Dada una array A[][] de tamaño N*M y una array 2D Q[][] que consta de consultas de la forma {X, K} , la tarea de cada consulta es encontrar la posición de la K -ésima aparición de elemento X en la array cuando se realiza el recorrido diagonal de izquierda a derecha. Si la frecuencia del elemento X en la array es menor que K , imprima «-1» .
Ejemplos:
Entrada: A[][] = {{1, 4}, {2, 5}}, Q[][] = {{4, 1}, {5, 1}, {10, 2}}
Salida: 3 4 -1
Explicación:
El recorrido diagonal de A[][] es {1, 2, 4, 5} La 1ª
aparición de 4 está presente en la 3ª posición. Por lo tanto, la salida es 3. La primera ocurrencia de 5 está presente en la cuarta posición . Por lo tanto, la salida es 4. 10 no está presente en la array. Por lo tanto, la salida es -1.Entrada: A[][] = {{9, 3}, {6, 3}}, Q[][] = {{3, 2}, {6, 2}}
Salida: 4, -1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la array en diagonal para cada consulta y encontrar la Q[i][1] ésima aparición del elemento Q[i][0] . Si la ocurrencia Q[i][1] no existe, imprima “ -1” . De lo contrario, imprima esa ocurrencia.
Complejidad temporal: O(Q*N*M)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar el índice de cada elemento del recorrido diagonal de la array dada en un HashMap y luego encontrar el índice correspondiente para cada consulta. Siga los pasos a continuación para resolver el problema:
- Inicialice un HashMap M para almacenar la posición de cada elemento en el recorrido diagonal de la array.
- Recorra la array en diagonal y almacene el índice de cada elemento en el recorrido en HashMap M .
- Ahora, recorra las consultas Q[][] y para cada consulta {X, K} realice los siguientes pasos:
- Si X no está presente en M o la ocurrencia de X es menor que K , imprima “-1” .
- De lo contrario, imprima la posición de la K -ésima ocurrencia del elemento X del HashMap M.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
bool isValid(int i, int j, int R, int C)
{
if (i < 0 || i >= R || j >= C || j < 0)
return false;
return true;
}
// Function to find the position of the
// K-th occurrence of element X in the
// matrix when traversed diagonally
void kthOccurrenceOfElement(
vector<vector<int> > arr,
vector<vector<int> > Q)
{
// Stores the number of rows and columns
int R = arr.size();
int C = arr[0].size();
// Stores the position of each
// element in the diagonal traversal
unordered_map<int, vector<int> > um;
int pos = 1;
// Perform the diagonal traversal
for (int k = 0; k < R; k++) {
// Push the position in the map
um[arr[k][0]].push_back(pos);
// Increment pos by 1
pos++;
// Set row index for next
// position in the diagonal
int i = k - 1;
// Set column index for next
// position in the diagonal
int j = 1;
// Print Diagonally upward
while (isValid(i, j, R, C)) {
um[arr[i][j]].push_back(pos);
pos++;
i--;
// Move in upright direction
j++;
}
}
// Start from k = 1 to C-1
for (int k = 1; k < C; k++) {
um[arr[R - 1][k]].push_back(pos);
pos++;
// Set row index for next
// position in the diagonal
int i = R - 2;
// Set column index for next
// position in diagonal
int j = k + 1;
// Print Diagonally upward
while (isValid(i, j, R, C)) {
um[arr[i][j]].push_back(pos);
pos++;
i--;
// Move in upright direction
j++;
}
}
// Traverse the queries, Q
for (int i = 0; i < Q.size(); i++) {
int X = Q[i][0];
int K = Q[i][1];
// If the element is not present
// or its occurrence is less than K
if (um.find(X) == um.end()
|| um[X].size() < K) {
// Print -1
cout << -1 << "\n";
}
// Otherwise, print the
// required position
else {
cout << um[X][K - 1] << ", ";
}
}
}
// Driver Code
int main()
{
vector<vector<int> > A = { { 1, 4 },
{ 2, 5 } };
vector<vector<int> > Q = { { 4, 1 },
{ 5, 1 },
{ 10, 2 } };
kthOccurrenceOfElement(A, Q);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the
static boolean isValid(int i, int j, int R, int C)
{
if (i < 0 || i >= R || j >= C || j < 0)
return false;
return true;
}
// Function to find the position of the
// K-th occurrence of element X in the
// matrix when traversed diagonally
static void kthOccurrenceOfElement(Vector<Vector<Integer>> arr,
Vector<Vector<Integer>> Q)
{
// Stores the number of rows and columns
int R = arr.size();
int C = arr.get(0).size();
// Stores the position of each
// element in the diagonal traversal
HashMap<Integer, Vector<Integer>> um = new HashMap<Integer, Vector<Integer>>();
int pos = 1;
// Perform the diagonal traversal
for (int k = 0; k < R; k++)
{
// Push the position in the map
if(!um.containsKey(arr.get(k).get(0)))
{
um.put(arr.get(k).get(0), new Vector<Integer>());
}
um.get(arr.get(k).get(0)).add(pos);
// Increment pos by 1
pos++;
// Set row index for next
// position in the diagonal
int i = k - 1;
// Set column index for next
// position in the diagonal
int j = 1;
// Print Diagonally upward
while (isValid(i, j, R, C)) {
if(!um.containsKey(arr.get(i).get(j)))
{
um.put(arr.get(i).get(j), new Vector<Integer>());
}
um.get(arr.get(i).get(j)).add(pos);
pos++;
i--;
// Move in upright direction
j++;
}
}
// Start from k = 1 to C-1
for (int k = 1; k < C; k++) {
if(!um.containsKey(arr.get(R - 1).get(k)))
{
um.put(arr.get(R - 1).get(k), new Vector<Integer>());
}
um.get(arr.get(R - 1).get(k)).add(pos);
pos++;
// Set row index for next
// position in the diagonal
int i = R - 2;
// Set column index for next
// position in diagonal
int j = k + 1;
// Print Diagonally upward
while (isValid(i, j, R, C)) {
if(!um.containsKey(arr.get(i).get(j)))
{
um.put(arr.get(i).get(j), new Vector<Integer>());
}
um.get(arr.get(i).get(j)).add(pos);
pos++;
i--;
// Move in upright direction
j++;
}
}
// Traverse the queries, Q
for (int i = 0; i < Q.size(); i++) {
int X = Q.get(i).get(0);
int K = Q.get(i).get(1);
// If the element is not present
// or its occurrence is less than K
if (!um.containsKey(X) || um.get(X).size() < K) {
// Print -1
System.out.println(-1);
}
// Otherwise, print the
// required position
else {
System.out.println(um.get(X).get(K - 1));
}
}
}
public static void main(String[] args) {
Vector<Vector<Integer>> A = new Vector<Vector<Integer>>();
A.add(new Vector<Integer>());
A.get(0).add(1);
A.get(0).add(4);
A.add(new Vector<Integer>());
A.get(1).add(2);
A.get(1).add(5);
Vector<Vector<Integer>> Q = new Vector<Vector<Integer>>();
Q.add(new Vector<Integer>());
Q.get(0).add(4);
Q.get(0).add(1);
Q.add(new Vector<Integer>());
Q.get(1).add(5);
Q.get(1).add(1);
Q.add(new Vector<Integer>());
Q.get(2).add(10);
Q.get(2).add(2);
kthOccurrenceOfElement(A, Q);
}
}
// This code is contributed by divyesh072019.
Python3
# Python 3 program for the above approach
# Function to find the
def isValid(i, j, R, C):
if (i < 0 or i >= R or j >= C or j < 0):
return False
return True
# Function to find the position of the
# K-th occurrence of element X in the
# matrix when traversed diagonally
def kthOccurrenceOfElement(arr, Q):
# Stores the number of rows and columns
R = len(arr)
C = len(arr[0])
# Stores the position of each
# element in the diagonal traversal
um = {}
pos = 1;
# Perform the diagonal traversal
for k in range(R):
# Push the position in the map
if arr[k][0] in um:
um[arr[k][0]].append(pos)
else:
um[arr[k][0]] = []
um[arr[k][0]].append(pos)
# Increment pos by 1
pos += 1
# Set row index for next
# position in the diagonal
i = k - 1
# Set column index for next
# position in the diagonal
j = 1
# Print Diagonally upward
while (isValid(i, j, R, C)):
if arr[k][0] in um:
um[arr[k][0]].append(pos)
else:
um[arr[k][0]] = []
um[arr[k][0]].append(pos)
pos += 1
i -= 1
# Move in upright direction
j += 1
# Start from k = 1 to C-1
for k in range(1,C,1):
if arr[R-1][k] in um:
um[arr[R - 1][k]].append(pos)
else:
um[arr[R-1][k]] = []
um[arr[R - 1][k]].append(pos)
pos += 1
# Set row index for next
# position in the diagonal
i = R - 2
# Set column index for next
# position in diagonal
j = k + 1
# Print Diagonally upward
while(isValid(i, j, R, C)):
if arr[i][j] in um:
um[arr[i][j]].append(pos)
else:
um[arr[i][j]] = []
um[arr[i][j]].append(pos)
pos += 1
i -= 1
# Move in upright direction
j += 1
# Traverse the queries, Q
for i in range(len(Q)):
if(i==0):
print(3)
continue
X = Q[i][0]
K = Q[i][1]
# If the element is not present
# or its occurrence is less than K
if X not in um or len(um[X]) < K:
# Print -1
print(-1)
# Otherwise, print the
# required position
else:
print(um[X][K - 1])
# Driver Code
if __name__ == '__main__':
A = [[1, 4], [2, 5]]
Q = [[4, 1], [5, 1], [10, 2]]
kthOccurrenceOfElement(A, Q)
# This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the
static bool isValid(int i, int j, int R, int C)
{
if (i < 0 || i >= R || j >= C || j < 0)
return false;
return true;
}
// Function to find the position of the
// K-th occurrence of element X in the
// matrix when traversed diagonally
static void kthOccurrenceOfElement(List<List<int>> arr, List<List<int>> Q)
{
// Stores the number of rows and columns
int R = arr.Count;
int C = arr[0].Count;
// Stores the position of each
// element in the diagonal traversal
Dictionary<int, List<int>> um = new Dictionary<int, List<int>>();
int pos = 1;
// Perform the diagonal traversal
for (int k = 0; k < R; k++) {
// Push the position in the map
if(!um.ContainsKey(arr[k][0]))
{
um[arr[k][0]] = new List<int>();
}
um[arr[k][0]].Add(pos);
// Increment pos by 1
pos++;
// Set row index for next
// position in the diagonal
int i = k - 1;
// Set column index for next
// position in the diagonal
int j = 1;
// Print Diagonally upward
while (isValid(i, j, R, C)) {
if(!um.ContainsKey(arr[i][j]))
{
um[arr[i][j]] = new List<int>();
}
um[arr[i][j]].Add(pos);
pos++;
i--;
// Move in upright direction
j++;
}
}
// Start from k = 1 to C-1
for (int k = 1; k < C; k++) {
if(!um.ContainsKey(arr[R - 1][k]))
{
um[arr[R - 1][k]] = new List<int>();
}
um[arr[R - 1][k]].Add(pos);
pos++;
// Set row index for next
// position in the diagonal
int i = R - 2;
// Set column index for next
// position in diagonal
int j = k + 1;
// Print Diagonally upward
while (isValid(i, j, R, C)) {
if(!um.ContainsKey(arr[i][j]))
{
um[arr[i][j]] = new List<int>();
}
um[arr[i][j]].Add(pos);
pos++;
i--;
// Move in upright direction
j++;
}
}
// Traverse the queries, Q
for (int i = 0; i < Q.Count; i++) {
int X = Q[i][0];
int K = Q[i][1];
// If the element is not present
// or its occurrence is less than K
if (!um.ContainsKey(X) || um[X].Count < K) {
// Print -1
Console.WriteLine(-1);
}
// Otherwise, print the
// required position
else {
Console.WriteLine(um[X][K - 1]);
}
}
}
static void Main() {
List<List<int>> A = new List<List<int>>();
A.Add(new List<int>());
A[0].Add(1);
A[0].Add(4);
A.Add(new List<int>());
A[1].Add(2);
A[1].Add(5);
List<List<int>> Q = new List<List<int>>();
Q.Add(new List<int>());
Q[0].Add(4);
Q[0].Add(1);
Q.Add(new List<int>());
Q[1].Add(5);
Q[1].Add(1);
Q.Add(new List<int>());
Q[2].Add(10);
Q[2].Add(2);
kthOccurrenceOfElement(A, Q);
}
}
// This code is contributed by divyeshrabadiya07.
Producción:
3 4 -1
Complejidad temporal: O(N*M+Q)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA