Dadas dos arrays ordenadas. Solo hay 1 diferencia entre las arrays. La primera array tiene un elemento adicional agregado en el medio. Encuentre el índice del elemento adicional.
Ejemplos:
Input: {2, 4, 6, 8, 9, 10, 12}; {2, 4, 6, 8, 10, 12}; Output: 4 Explanation: The first array has an extra element 9. The extra element is present at index 4. Input: {3, 5, 7, 9, 11, 13} {3, 5, 7, 11, 13} Output: 3 Explanation: The first array has an extra element 9. The extra element is present at index 3.
Método 1: Esto incluye el enfoque básico para resolver este problema en particular.
Enfoque: el método básico es iterar a través de toda la segunda array y verificar elemento por elemento si son diferentes. A medida que se ordena la array, la verificación de la posición adyacente de dos arrays debe ser similar hasta que se encuentre el elemento que falta.
Algoritmo:
- Atraviesa la array de principio a fin.
- Compruebe si el elemento en el i-ésimo elemento de las dos arrays es similar o no.
- Si los elementos no son similares, imprima el índice y rompa
Implementación:
C++
// C++ program to find an extra // element present in arr1[] #include <iostream> using namespace std; // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. int findExtra(int arr1[], int arr2[], int n) { for (int i = 0; i < n; i++) if (arr1[i] != arr2[i]) return i; return n; } // Driver code int main() { int arr1[] = {2, 4, 6, 8, 10, 12, 13}; int arr2[] = {2, 4, 6, 8, 10, 12}; int n = sizeof(arr2) / sizeof(arr2[0]); // Solve is passed both arrays cout << findExtra(arr1, arr2, n); return 0; }
Java
// Java program to find an extra // element present in arr1[] class GFG { // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. static int findExtra(int arr1[], int arr2[], int n) { for (int i = 0; i < n; i++) if (arr1[i] != arr2[i]) return i; return n; } // Driver Code public static void main (String[] args) { int arr1[] = {2, 4, 6, 8, 10, 12, 13}; int arr2[] = {2, 4, 6, 8, 10, 12}; int n = arr2.length; // Solve is passed both arrays System.out.println(findExtra(arr1, arr2, n)); } } // This code is contributed by Harsh Agarwal
Python3
# Python 3 program to find an # extra element present in arr1[] # Returns index of extra . # element in arr1[] n is # size of arr2[]. Size of # arr1[] is n-1. def findExtra(arr1, arr2, n) : for i in range(0, n) : if (arr1[i] != arr2[i]) : return i return n # Driver code arr1 = [2, 4, 6, 8, 10, 12, 13] arr2 = [2, 4, 6, 8, 10, 12] n = len(arr2) # Solve is passed both arrays print(findExtra(arr1, arr2, n)) # This code is contributed # by Nikita Tiwari.
C#
// C# program to find an extra // element present in arr1[] using System; class GfG { // Returns index of extra // element in arr1[]. n is // size of arr2[]. Size of // arr1[] is n-1. static int findExtra(int []arr1, int []arr2, int n) { for (int i = 0; i < n; i++) if (arr1[i] != arr2[i]) return i; return n; } // Driver code public static void Main () { int []arr1 = {2, 4, 6, 8, 10, 12, 13}; int []arr2 = {2, 4, 6, 8, 10, 12}; int n = arr2.Length; // Solve is passed both arrays Console.Write(findExtra(arr1, arr2, n)); } } // This code is contributed by parashar.
PHP
<?php // PHP program to find an extra // element present in arr1[] // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. function findExtra($arr1, $arr2, $n) { for ($i = 0; $i < $n; $i++) if ($arr1[$i] != $arr2[$i]) return $i; return $n; } // Driver code $arr1 = array (2, 4, 6, 8, 10, 12, 13); $arr2 = array(2, 4, 6, 8, 10, 12); $n = sizeof($arr2); // Solve is passed // both arrays echo findExtra($arr1, $arr2, $n); // This code is contributed by ajit ?>
Javascript
<script> // JavaScript program to find an extra // element present in arr1[] // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. function findExtra(arr1, arr2, n) { for (let i = 0; i < n; i++) if (arr1[i] != arr2[i]) return i; return n; } // Driver code let arr1 = [2, 4, 6, 8, 10, 12, 13]; let arr2 = [2, 4, 6, 8, 10, 12]; let n = arr2.length; // Solve is passed both arrays document.write(findExtra(arr1, arr2, n)); // This code is contributed by Surbhi Tyagi. </script>
6
Análisis de Complejidad:
- Complejidad temporal: O(n).
Como se necesita un recorrido a través de la array, la complejidad del tiempo es lineal. - Complejidad espacial: O(1).
Dado que no se requiere espacio adicional, la complejidad del tiempo es constante.
Método 2: Este método es una mejor manera de resolver el problema anterior y utiliza el concepto de búsqueda binaria.
Enfoque: Para encontrar el índice del elemento faltante en menos de un tiempo lineal, se puede usar la búsqueda binaria, la idea es que todos los índices mayores o iguales al índice del elemento faltante tendrán diferentes elementos tanto en las arrays como en todos los los índices menores que ese índice tendrán elementos similares en ambas arrays.
Algoritmo:
- Cree tres variables, bajo = 0 , alto = n-1 , medio , ans = n
- Ejecute un ciclo hasta que el mínimo sea menor o igual que el máximo, es decir, hasta que nuestro rango de búsqueda sea menor que cero.
- Si el elemento medio, es decir, (bajo + alto)/2, de ambas arrays es similar, actualice la búsqueda a la segunda mitad del rango de búsqueda, es decir, bajo = medio + 1
- De lo contrario, actualice la búsqueda a la primera mitad del rango de búsqueda, es decir, alto = medio – 1 , y actualice la respuesta al índice actual, ans = medio
- Imprime el índice.
Implementación:
C++
// C++ program to find an extra // element present in arr1[] #include <iostream> using namespace std; // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. int findExtra(int arr1[], int arr2[], int n) { // Initialize result int index = n; // left and right are end // points denoting the current range. int left = 0, right = n - 1; while (left <= right) { int mid = (left + right) / 2; // If middle element is same // of both arrays, it means // that extra element is after // mid so we update left to mid+1 if (arr2[mid] == arr1[mid]) left = mid + 1; // If middle element is different // of the arrays, it means that // the index we are searching for // is either mid, or before mid. // Hence we update right to mid-1. else { index = mid; right = mid - 1; } } // when right is greater than // left our search is complete. return index; } // Driver code int main() { int arr1[] = {2, 4, 6, 8, 10, 12, 13}; int arr2[] = {2, 4, 6, 8, 10, 12}; int n = sizeof(arr2) / sizeof(arr2[0]); // Solve is passed both arrays cout << findExtra(arr1, arr2, n); return 0; }
Java
// Java program to find an extra // element present in arr1[] class GFG { // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. static int findExtra(int arr1[], int arr2[], int n) { // Initialize result int index = n; // left and right are end // points denoting the current range. int left = 0, right = n - 1; while (left <= right) { int mid = (left+right) / 2; // If middle element is same // of both arrays, it means // that extra element is after // mid so we update left to mid+1 if (arr2[mid] == arr1[mid]) left = mid + 1; // If middle element is different // of the arrays, it means that // the index we are searching for // is either mid, or before mid. // Hence we update right to mid-1. else { index = mid; right = mid - 1; } } // when right is greater than // left, our search is complete. return index; } // Driver Code public static void main (String[] args) { int arr1[] = {2, 4, 6, 8, 10, 12,13}; int arr2[] = {2, 4, 6, 8, 10, 12}; int n = arr2.length; // Solve is passed both arrays System.out.println(findExtra(arr1, arr2, n)); } } // This code is contributed by Harsh Agarwal
Python3
# Python3 program to find an extra # element present in arr1[] # Returns index of extra element # in arr1[]. n is size of arr2[]. # Size of arr1[] is n-1. def findExtra(arr1, arr2, n) : index = n # Initialize result # left and right are end points # denoting the current range. left = 0 right = n - 1 while (left <= right) : mid = (int)((left + right) / 2) # If middle element is same # of both arrays, it means # that extra element is after # mid so we update left to # mid + 1 if (arr2[mid] == arr1[mid]) : left = mid + 1 # If middle element is different # of the arrays, it means that # the index we are searching for # is either mid, or before mid. # Hence we update right to mid-1. else : index = mid right = mid - 1 # when right is greater than left our # search is complete. return index # Driver code arr1 = [2, 4, 6, 8, 10, 12, 13] arr2 = [2, 4, 6, 8, 10, 12] n = len(arr2) # Solve is passed both arrays print(findExtra(arr1, arr2, n)) # This code is contributed by Nikita Tiwari.
C#
// C# program to find an extra // element present in arr1[] using System; class GFG { // Returns index of extra // element in arr1[]. n is // size of arr2[]. // Size of arr1[] is // n - 1. static int findExtra(int []arr1, int []arr2, int n) { // Initialize result int index = n; // left and right are // end points denoting // the current range. int left = 0, right = n - 1; while (left <= right) { int mid = (left+right) / 2; // If middle element is // same of both arrays, // it means that extra // element is after mid // so we update left // to mid + 1 if (arr2[mid] == arr1[mid]) left = mid + 1; // If middle element is // different of the arrays, // it means that the index // we are searching for is // either mid, or before mid. // Hence we update right to mid-1. else { index = mid; right = mid - 1; } } // when right is greater // than left our // search is complete. return index; } // Driver Code public static void Main () { int []arr1 = {2, 4, 6, 8, 10, 12,13}; int []arr2 = {2, 4, 6, 8, 10, 12}; int n = arr2.Length; // Solve is passed // both arrays Console.Write(findExtra(arr1, arr2, n)); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP program to find an extra // element present in arr1[] // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. function findExtra($arr1, $arr2, $n) { // Initialize result $index = $n; // left and right are // end points denoting // the current range. $left = 0; $right = $n - 1; while ($left <= $right) { $mid = ($left+$right) / 2; // If middle element is same // of both arrays, it means // that extra element is after // mid so we update left to mid+1 if ($arr2[$mid] == $arr1[$mid]) $left = $mid + 1; // If middle element is different // of the arrays, it means that the // index we are searching for is either // mid, or before mid. Hence we update // right to mid-1. else { $index = $mid; $right = $mid - 1; } } // when right is greater than // left, our search is complete. return $index; } // Driver code { $arr1 = array(2, 4, 6, 8, 10, 12, 13); $arr2 = array(2, 4, 6, 8, 10, 12); $n = sizeof($arr2) / sizeof($arr2[0]); // Solve is passed both arrays echo findExtra($arr1, $arr2, $n); return 0; } // This code is contributed by nitin mittal ?>
Javascript
<script> // Javascript program to find an extra // element present in arr1[] // Returns index of extra element // in arr1[]. n is size of arr2[]. // Size of arr1[] is n-1. function findExtra( arr1, arr2, n) { // Initialize result let index = n; // left and right are end // points denoting the current range. let left = 0, right = n - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); // If middle element is same // of both arrays, it means // that extra element is after // mid so we update left to mid+1 if (arr2[mid] == arr1[mid]) left = mid + 1; // If middle element is different // of the arrays, it means that // the index we are searching for // is either mid, or before mid. // Hence we update right to mid-1. else { index = mid; right = mid - 1; } } // when right is greater than // left our search is complete. return index; } // Driver program let arr1 = [2, 4, 6, 8, 10, 12, 13]; let arr2 = [2, 4, 6, 8, 10, 12]; let n = arr2.length; // Solve is passed both arrays document.write(findExtra(arr1, arr2, n)); </script>
6
Análisis de Complejidad:
- Complejidad temporal: O(log n).
La complejidad temporal de la búsqueda binaria es O(log n) - Complejidad espacial : O(1).
Como no se requiere espacio adicional, la complejidad del tiempo es constante.
Método 3: Este método resuelve el problema dado usando la función predefinida.
Enfoque: para encontrar el elemento que es diferente, encuentre la suma de cada array y reste las sumas y encuentre el valor absoluto. Busque la array más grande y verifique si el absoluto es igual a un índice y devuelva ese índice. Si falta un elemento y todos los demás elementos son iguales, entonces la diferencia de sumas será igual al elemento faltante.
Algoritmo:
- Crea una función para calcular la suma de dos arrays.
- Encuentre la diferencia absoluta entre la suma de dos arrays ( valor ).
- Atraviesa la array más grande desde el principio hasta el final
- Si el elemento en cualquier índice es igual al valor, imprima el índice y rompa el ciclo.
Implementación:
C++
// C++ code for above approach #include<bits/stdc++.h> using namespace std; // function return sum of array elements int sum(int arr[], int n) { int summ = 0; for (int i = 0; i < n; i++) { summ += arr[i]; } return summ; } // function return index of given element int indexOf(int arr[], int element, int n) { for (int i = 0; i < n; i++) { if (arr[i] == element) { return i; } } return -1; } // Function to find Index int find_extra_element_index(int arrA[], int arrB[], int n, int m) { // Calculating extra element int extra_element = sum(arrA, n) - sum(arrB, m); // returns index of extra element return indexOf(arrA, extra_element, n); } // Driver Code int main() { int arrA[] = {2, 4, 6, 8, 10, 12, 13}; int arrB[] = {2, 4, 6, 8, 10, 12}; int n = sizeof(arrA) / sizeof(arrA[0]); int m = sizeof(arrB) / sizeof(arrB[0]); cout << find_extra_element_index(arrA, arrB, n, m); } // This code is contributed by mohit kumar
Java
// Java code for above approach class GFG { // Function to find Index static int find_extra_element_index(int[] arrA, int[] arrB) { // Calculating extra element int extra_element = sum(arrA) - sum(arrB); // returns index of extra element return indexOf(arrA, extra_element); } // function return sum of array elements static int sum(int[] arr) { int sum = 0; for (int i = 0; i < arr.length; i++) { sum += arr[i]; } return sum; } // function return index of given element static int indexOf(int[] arr, int element) { for (int i = 0; i < arr.length; i++) { if (arr[i] == element) { return i; } } return -1; } // Driver Code public static void main(String[] args) { int[] arrA = {2, 4, 6, 8, 10, 12, 13}; int[] arrB = {2, 4, 6, 8, 10, 12}; System.out.println(find_extra_element_index(arrA, arrB)); } } /* This code contributed by PrinciRaj1992 */
Python3
# Python3 code for above approach # Function to find Index def find_extra_element_index(arrA, arrB): # Calculating extra element extra_element = sum(arrA) - sum(arrB) # returns index of extra element return arrA.index(extra_element) # Driver Code arrA = [2, 4, 6, 8, 10, 12, 13] arrB = [2, 4, 6, 8, 10, 12] print(find_extra_element_index(arrA,arrB)) # This code is contributed by Dravid
C#
// C# code for above approach using System; class GFG { // Function to find Index static int find_extra_element_index(int[] arrA, int[] arrB) { // Calculating extra element int extra_element = sum(arrA) - sum(arrB); // returns index of extra element return indexOf(arrA, extra_element); } // function return sum of array elements static int sum(int[] arr) { int sum = 0; for (int i = 0; i < arr.Length; i++) { sum += arr[i]; } return sum; } // function return index of given element static int indexOf(int[] arr, int element) { for (int i = 0; i < arr.Length; i++) { if (arr[i] == element) { return i; } } return -1; } // Driver Code public static void Main(String[] args) { int[] arrA = {2, 4, 6, 8, 10, 12, 13}; int[] arrB = {2, 4, 6, 8, 10, 12}; Console.WriteLine(find_extra_element_index(arrA, arrB)); } } // This code has been contributed by 29AjayKumar
Javascript
<script> // Javascript code for above approach // Function to find Index function find_extra_element_index(arrA, arrB) { // Calculating extra element let extra_element = sum(arrA) - sum(arrB); // returns index of extra element return indexOf(arrA, extra_element); } // function return sum of array elements function sum(arr) { let sum = 0; for (let i = 0; i < arr.length; i++) { sum += arr[i]; } return sum; } // function return index of given element function indexOf(arr, element) { for (let i = 0; i < arr.length; i++) { if (arr[i] == element) { return i; } } return -1; } let arrA = [2, 4, 6, 8, 10, 12, 13]; let arrB = [2, 4, 6, 8, 10, 12]; document.write(find_extra_element_index(arrA, arrB)); </script>
6
Análisis de Complejidad:
- Complejidad temporal: O(n).
Dado que solo se necesitan tres recorridos a través de la array, la complejidad del tiempo es lineal. - Complejidad espacial: O(1).
Como no se requiere espacio adicional, la complejidad del tiempo es constante.
Este artículo es una contribución de Abhishek Khatri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA