Dada una array A[] de N enteros. Considere un número entero tal que num aparece en la array A[] y todas las posiciones de num , ordenadas en orden creciente forman una progresión aritmética . La tarea es imprimir todos esos pares de números junto con la diferencia común de las progresiones aritméticas que forman.
Ejemplos:
Entrada: N = 8, A = {1, 2, 1, 3, 1, 2, 1, 5}
Salida: {1, 2}, {2, 4}, {3, 0}, {5, 0}
Explicación: Las posiciones en las que aparece 1 son: 0, 2, 4, 6
Se puede ver fácilmente que todas las posiciones tienen la misma diferencia entre elementos consecutivos (es decir, 2).
Por lo tanto, las posiciones de 1 forman progresión aritmética con diferencia común 2.
De manera similar, todas las posiciones de 2 forman progresión aritmética con diferencia común 4.
Y, 3 y 5 están presentes solo una vez.
De acuerdo con la definición de progresión aritmética (o AP), las secuencias de un solo elemento también son AP con diferencia común 0.Entrada: N = 1, A = {1}
Salida: {1, 0}
Enfoque: La idea para resolver el problema es mediante el uso de Hashing .
Siga los pasos para resolver el problema:
- Cree un mapa que tenga un número entero como clave y un vector de números enteros como valor de la clave.
- Atraviese la array y almacene todas las posiciones de cada elemento presente en la array en el mapa .
- Iterar a través del mapa y verificar si todas las posiciones del elemento actual en el mapa forman AP
- Si es así, inserte ese elemento junto con la diferencia común en la respuesta.
- De lo contrario, continúe iterando a través del mapa
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for above approach #include <bits/stdc++.h> using namespace std; // Function to print all elements // in given array whose positions forms // arithmetic progression void printAP(int N, int A[]) { // Declaring a hash table(or map) // to store positions of all elements unordered_map<int, vector<int> > pos; // Storing positions of // array elements in map for (int i = 0; i < N; i++) { pos[A[i]].push_back(i); } // Declaring a map to store answer // i.e. key - value pair of element // with their positions forming A.P. // and their common difference map<int, int> ans; // Iterating through the map "pos" for (auto x : pos) { // If current element is present // only at 1 position, then simply // insert the element in answer // with common difference = 0 if (x.second.size() == 1) { ans[x.first] = 0; } // If current element is present // at more than one positions, // then check if all the // positions are at same difference else { bool flag = 1; // Storing the difference of // first two positions in // variable "diff" int diff = x.second[1] - x.second[0]; // Declaring "prev" to store // previous position of // current element int prev = x.second[1]; //"curr" stores the // Current position of the element int curr; // Iterating through all the // positions of the current element // and checking id they are in A.P. for (auto it = 2; it < x.second.size(); it++) { curr = x.second[it]; if (curr - prev != diff) { flag = 0; break; } prev = x.second[it]; } // If all positions of current // element are in A.P. // Insert it into answer with // common difference as "diff" if (flag == 1) { ans[x.first] = diff; } } } // Printing the answer for (auto it : ans) { cout << it.first << " " << it.second << endl; } } // Driver Code int main() { int N = 8; int A[] = { 1, 2, 1, 3, 1, 2, 1, 5 }; printAP(N, A); }
Python3
## Function to print all elements ## in given array whose positions forms ## arithmetic progression def printAP(N, A): ## Declaring a dict ## to store positions of all elements pos = {} ## Storing positions of ## array elements in dict for i in range(N): if(A[i] not in pos): pos[A[i]] = [] pos[A[i]].append(i) ## Declaring a dict to store answer ## i.e. key - value pair of element ## with their positions forming A.P. ## and their common difference ans = {} ## Iterating through the doct "pos" for x in pos: ## If current element is present ## only at 1 position, then simply ## insert the element in answer ## with common difference = 0 if (len(pos[x]) == 1): ans[x] = 0 ## If current element is present ## at more than one positions, ## then check if all the ## positions are at same difference else: flag = 1 ## Storing the difference of ## first two positions in ## variable "diff" diff = pos[x][1]-pos[x][0] ## Declaring "prev" to store ## previous position of ## current element prev = pos[x][1]; ## "curr" stores the ## Current position of the element curr = 0 length = len(pos[x]) ## Iterating through all the ## positions of the current element ## and checking id they are in A.P. for it in range(2, length): curr = pos[x][it]; if (curr - prev != diff): flag = 0; break; prev = curr ## If all positions of current ## element are in A.P. ## Insert it into answer with ## common difference as "diff" if (flag == 1): ans[x] = diff for x in ans: print(x, ans[x]) ## Driver code if __name__=='__main__': N = 8 A = [1, 2, 1, 3, 1, 2, 1, 5] printAP(N, A) # This code is contributed by subhamgoyal2014.
Javascript
<script> // JavaScript code for above approach // Function to print all elements // in given array whose positions forms // arithmetic progression const printAP = (N, A) => { // Declaring a hash table(or map) // to store positions of all elements let pos = {}; // Storing positions of // array elements in map for (let i = 0; i < N; i++) { if (A[i] in pos) pos[A[i]].push(i); else pos[A[i]] = [i]; } // Declaring a map to store answer // i.e. key - value pair of element // with their positions forming A.P. // and their common difference let ans = {}; // Iterating through the map "pos" for (let x in pos) { // If current element is present // only at 1 position, then simply // insert the element in answer // with common difference = 0 if (pos[x].length == 1) { ans[x] = 0; } // If current element is present // at more than one positions, // then check if all the // positions are at same difference else { let flag = 1; // Storing the difference of // first two positions in // variable "diff" let diff = pos[x][1] - pos[x][0]; // Declaring "prev" to store // previous position of // current element let prev = pos[x][1]; //"curr" stores the // Current position of the element let curr; // Iterating through all the // positions of the current element // and checking id they are in A.P. for (let it = 2; it < pos[x].length; it++) { curr = pos[x][it]; if (curr - prev != diff) { flag = 0; break; } prev = pos[x][it]; } // If all positions of current // element are in A.P. // Insert it into answer with // common difference as "diff" if (flag == 1) { ans[x] = diff; } } } // Printing the answer for (let it in ans) { document.write(`${it} ${ans[it]}<br/>`); } } // Driver Code let N = 8; let A = [1, 2, 1, 3, 1, 2, 1, 5]; printAP(N, A); // This code is contributed by rakeshsahni </script>
1 2 2 4 3 0 5 0
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA