Запросы на поиск крайнего левого целого числа данного типа в двоичном массиве
Опубликовано: 12 Января, 2022
Учитывая двоичный массив arr [] , задача состоит в том, чтобы спроектировать структуру данных, которая поддерживает следующие операции в O (1).
- Тип 1: удалите и распечатайте крайний левый 0 из массива.
- Тип 2: Удалить и распечатать крайний левый 1 из массива.
- Тип 3: удалите и распечатайте крайний левый элемент массива.
Если какой-либо из запрошенных элементов отсутствует в массиве, выведите -1.
Примеры:
Input: arr[] = {1, 0, 1, 1, 1}, q[] = {1, 3, 1}
Output:
0
1
-1
Type 1 query: Print 0 and the array become {1, 1, 1, 1}
Type 3 query: Print 1, arr[] = {1, 1, 1}
Type 1 query: There are no 0s left, so print -1Input: arr[] = {1, 0, 1, 0, 1}, q[] = {3, 3, 3}
Output:
1
0
1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Наивный подход: простой подход - вставить все элементы в очередь, которая поддерживает функцию «первым пришел - первым обслужен». Этот подход будет работать в O (1) для поиска самого левого элемента в массиве, но он не может найти крайний левый 1 или крайний левый 0 в O (1).
Эффективный подход: создайте две очереди, первая очередь будет хранить индексы нулей в порядке появления, а вторая очередь будет хранить индексы единиц в порядке появления. Теперь данные операции можно выполнять следующим образом:
- Тип 1: Распечатайте удаление заголовка первой очереди в O (1).
- Тип 2: Распечатайте удаление заголовка второй очереди в O (1).
- Тип 3: сравните заголовок обеих очередей и верните тот с минимальным индексом, а затем удалите его.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h>using namespace std; // To store the indices of 0s and 1s static queue<int> zero; static queue<int> one ; // Function to return the leftmost 0 static int getLeftMostZero() { // If there are no 0s if (zero.empty()) return -1; // pop the head of the queue zero.pop(); return 0; } // Function to return the leftmost 1 static int getLeftMostOne() { // If there are no 1s if (one.empty()) return -1; // pop the head of the queue one.pop(); return 1; } // Function to return the pre-calculate array // such that arr[i] stores the count of // valid numbers in the range [0, i] int getLeftMostElement() { // If there are no elements left if (zero.empty() && one.empty()) return -1; // If only 1s are there else if (zero.empty()) { one.pop(); return 1; } // If only 0s are there else if (one.empty()) { zero.pop(); return 0; } // Get the element which is at // the left-most position int res = (zero.front() < one.front()) ? 0 : 1; if (res == 0) zero.pop(); else one.pop(); return res; } // Function to perform the queries void performQueries(int arr[], int n, int queries[], int q) { for (int i = 0; i < n; i++) { if (arr[i] == 0) zero.push(i); else one.push(i); } // For every query for (int i = 0; i < q; i++) { // Get its type int type = queries[i]; switch (type) { // Perform type 1 query case 1: cout << (getLeftMostZero()) << endl; break; // Perform type 2 query case 2: cout << (getLeftMostOne()) << endl; break; // Perform type 3 query case 3: cout << (getLeftMostElement()) << endl; break; } } } // Driver code int main() { int arr[] = { 1, 0, 1, 1, 1 }; int n = sizeof(arr) / sizeof(int); int queries[] = { 1, 3, 1 }; int q = sizeof(queries) / sizeof(int); performQueries(arr, n, queries, q); } // This code is contributed by andrew1234 |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to return the leftmost 0 static int getLeftMostZero(Queue<Integer> zero) { // If there are no 0s if (zero.isEmpty()) return -1; // Remove the head of the queue zero.remove(); return 0; } // Function to return the leftmost 1 static int getLeftMostOne(Queue<Integer> one) { // If there are no 1s if (one.isEmpty()) return -1; // Remove the head of the queue one.remove(); return 1; } // Function to return the pre-calculate array // such that arr[i] stores the count of // valid numbers in the range [0, i] static int getLeftMostElement(Queue<Integer> zero, Queue<Integer> one) { // If there are no elements left if (zero.isEmpty() && one.isEmpty()) return -1; // If only 1s are there else if (zero.isEmpty()) { one.remove(); return 1; } // If only 0s are there else if (one.isEmpty()) { zero.remove(); return 0; } // Get the element which is at // the left-most position int res = (zero.peek() < one.peek()) ? 0 : 1; if (res == 0) zero.remove(); else one.remove(); return res; } // Function to perform the queries static void performQueries(int arr[], int n, int queries[], int q) { // To store the indices of 0s and 1s Queue<Integer> zero = new LinkedList<>(); Queue<Integer> one = new LinkedList<>(); for (int i = 0; i < n; i++) { if (arr[i] == 0) zero.add(i); else one.add(i); } // For every query for (int i = 0; i < q; i++) { // Get its type int type = queries[i]; switch (type) { // Perform type 1 query case 1: System.out.println(getLeftMostZero(zero)); break; // Perform type 2 query case 2: System.out.println(getLeftMostOne(one)); break; // Perform type 3 query case 3: System.out.println(getLeftMostElement(zero, one)); break; } } } // Driver code public static void main(String args[]) { int arr[] = { 1, 0, 1, 1, 1 }; int n = arr.length; int queries[] = { 1, 3, 1 }; int q = queries.length; performQueries(arr, n, queries, q); }} |
Python3
# Python3 implementation of the approachfrom collections import deque # To store the indices of 0s and 1szero = deque()one = deque() # Function to return the leftmost 0def getLeftMostZero(): # If there are no 0s if not len(zero): return -1 # pop the head of the queue zero.popleft() return 0 # Function to return the leftmost 1def getLeftMostOne(): # If there are no 1s if not len(one): return -1 # pop the head of the queue one.popleft() return 1 # Function to return the pre-calculate array# such that arr[i] stores the count of# valid numbers in the range [0, i]def getLeftMostElement(): # If there are no elements left if not len(zero) and not len(one): return -1 # If only 1s are there elif not len(zero): one.popleft() return 1 # If only 0s are there elif not len(one): zero.popleft() return 0 # Get the element which is at # the left-most position res = 0 if zero[0] < one[0] else 1 if res == 0: zero.popleft() else: one.popleft() return res # Function to perform the queriesdef performQueries(arr: list, n: int, queries: list, q: int): for i in range(n): if arr[i] == 0: zero.append(i) else: one.append(i) # For every query for i in range(q): # Get its type type = queries[i] # Perform type 1 query if type == 1: print(getLeftMostZero()) # Perform type 2 query elif type == 2: print(getLeftMostOne()) # Perform type 3 query elif type == 3: print(getLeftMostElement()) # Driver Codeif __name__ == "__main__": arr = [1, 0, 1, 1, 1] n = len(arr) queries = [1, 3, 1] q = len(queries) performQueries(arr, n, queries, q) # This code is contributed by# sanjeev2552 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ // Function to return the leftmost 0 static int getLeftMostZero(Queue<int> zero) { // If there are no 0s if (zero.Count == 0) return -1; // Remove the head of the queue zero.Dequeue(); return 0; } // Function to return the leftmost 1 static int getLeftMostOne(Queue<int> one) {РЕКОМЕНДУЕМЫЕ СТАТЬИ |