在大小为n的排序数组中查找唯一的重复元素-yiteyi-C++库

给定一个由n个元素组成的排序数组，其中包含从1到n-1的元素，即一个元素出现两次，任务是在数组中查找重复元素。 例如：

null

Input :  arr[] = { 1, 2 , 3 , 4 , 4}Output :  4Input :  arr[] = { 1 , 1 , 2 , 3 , 4}Output :  1

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 幼稚的方法 就是扫描整个数组，检查一个元素是否出现两次，然后返回。这种方法需要O（n）个时间。一 有效率的 方法是使用二进制搜索 .

观察：如果元素“X”重复，那么它必须位于数组中的索引“X”处。因此，问题简化为找到任何值与其索引相同的元素。

C++

                         // C++ program to find the only repeating element in an                       
                         // array of size n and elements from range 1 to n-1.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
           
                         // Returns index of second appearance of a repeating element                       
                         // The function assumes that array elements are in range from                       
                         // 1 to n-1.                       
                         int                                     FindRepeatingElement(                                     int                                     arr[],                                     int                                     size){                       
                                                 int                                     lo = 0;                       
                                                 int                                     hi = size - 1;                       
                                                 int                                     mid;                       
                                   
                                                 while                                     (lo <= hi){                       
                                                 mid = (lo+hi)/2;                       
                                   
                                                 if                                     (arr[mid] <= mid){                       
                                                 hi = mid-1;                       
                                                 }                       
                                                 else                                     {                       
                                                 lo = mid + 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     lo;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 2, 3, 3, 4, 5};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     index = findRepeatingElement(arr, n);                       
                                                 if                                     (index != -1)                       
                                                 cout << arr[index];                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the only repeating element in an                       
                         // array of size n and elements from range 1 to n-1.                       
           
                         class                                     Test                       
                         {                       
                                                 // Returns index of second appearance of a repeating element                       
                                                 // The function assumes that array elements are in range from                       
                                                 // 1 to n-1.                       
                                                 static                                     int                                     findRepeatingElement(                                     int                                     arr[],                                     int                                     low,                                     int                                     high)                       
                                                 {                       
                                                 // low = 0 , high = n-1;                       
                                                 if                                     (low > high)                       
                                                 return                                     -                                     1                                     ;                       
                                   
                                                 int                                     mid = (low + high) /                                     2                                     ;                       
                                   
                                                 // Check if the mid element is the repeating one                       
                                                 if                                     (arr[mid] != mid +                                     1                                     )                       
                                                 {                       
                                                 if                                     (mid >                                     0                                     && arr[mid]==arr[mid-                                     1                                     ])                       
                                                 return                                     mid;                       
                                   
                                                 // If mid element is not at its position that means                       
                                                 // the repeated element is in left                       
                                                 return                                     findRepeatingElement(arr, low, mid-                                     1                                     );                       
                                                 }                       
                                   
                                                 // If mid is at proper position then repeated one is in                       
                                                 // right.                       
                                                 return                                     findRepeatingElement(arr, mid+                                     1                                     , high);                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     };                       
                                                 int                                     index = findRepeatingElement(arr,                                     0                                     , arr.length-                                     1                                     );                       
                                                 if                                     (index != -                                     1                                     )                       
                                                 System.out.println(arr[index]);                       
                                                 }                       
                         }                       

Python3

                         # Python program to find the only repeating element in an                       
                         # array of size n and elements from range 1 to n-1                       
           
                         # Returns index of second appearance of a repeating element                       
                         # The function assumes that array elements are in range from                       
                         # 1 to n-1.                       
                         def                                     findRepeatingElement(arr, low, high):                       
           
                                                 # low = 0 , high = n-1                       
                                                 if                                     low > high:                       
                                                 return                                     -                                     1                       
           
                                                 mid                                     =                                     (low                                     +                                     high)                                     /                                     /                                     2                       
           
                                                 # Check if the mid element is the repeating one                       
                                                 if                                     (arr[mid] !                                     =                                     mid                                     +                                     1                                     ):                       
                                   
                                                 if                                     (mid >                                     0                                     and                                     arr[mid]                                     =                                     =                                     arr[mid                                     -                                     1                                     ]):                       
                                                 return                                     mid                       
           
                                                 # If mid element is not at its position that means                       
                                                 # the repeated element is in left                       
                                                 return                                     findRepeatingElement(arr, low, mid                                     -                                     1                                     )                       
           
                                                 # If mid is at proper position then repeated one is in                       
                                                 # right.                       
                                                 return                                     findRepeatingElement(arr, mid                                     +                                     1                                     , high)                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         index                                     =                                     findRepeatingElement(arr,                                     0                                     , n                                     -                                     1                                     )                       
                         if                                     (index                                     is                                     not                                     -                                     1                                     ):                       
                                                 print                                     (arr[index])                       
           
                         #This code is contributed by Afzal Ansari                       

C#

                         // C# program to find the only repeating                       
                         // element in an array of size n and                       
                         // elements from range 1 to n-1.                       
                         using                                     System;                       
           
                         class                                     Test                       
                         {                       
                                                 // Returns index of second appearance of a                       
                                                 // repeating element. The function assumes that                       
                                                 // array elements are in range from 1 to n-1.                       
                                                 static                                     int                                     findRepeatingElement(                                     int                                     []arr,                                     int                                     low,                       
                                                 int                                     high)                       
                                                 {                       
                                                 // low = 0 , high = n-1;                       
                                                 if                                     (low > high)                       
                                                 return                                     -1;                       
                                   
                                                 int                                     mid = (low + high) / 2;                       
                                   
                                                 // Check if the mid element                       
                                                 // is the repeating one                       
                                                 if                                     (arr[mid] != mid + 1)                       
                                                 {                       
                                                 if                                     (mid > 0 && arr[mid]==arr[mid-1])                       
                                                 return                                     mid;                       
                                   
                                                 // If mid element is not at its position                       
                                                 // that means the repeated element is in left                       
                                                 return                                     findRepeatingElement(arr, low, mid-1);                       
                                                 }                       
                                   
                                                 // If mid is at proper position                       
                                                 // then repeated one is in right.                       
                                                 return                                     findRepeatingElement(arr, mid+1, high);                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {1, 2, 3, 3, 4, 5};                       
                                                 int                                     index = findRepeatingElement(arr, 0, arr.Length-1);                       
                                                 if                                     (index != -1)                       
                                                 Console.Write(arr[index]);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // PHP program to find the only                       
                         // repeating element in an array                       
                         // of size n and elements from                       
                         // range 1 to n-1.                       
           
                         // Returns index of second                       
                         // appearance of a repeating                       
                         // element. The function assumes                       
                         // that array elements are in                       
                         // range from 1 to n-1.                       
                         function                                     findRepeatingElement(                                     $arr                                     ,                       
                                                 $low                                     ,                       
                                                 $high                                     )                       
                         {                       
                                                 // low = 0 , high = n-1;                       
                                                 if                                     (                                     $low                                     >                                     $high                                     )                       
                                                 return                                     -1;                       
           
                                                 $mid                                     =                                     floor                                     ((                                     $low                                     +                                     $high                                     ) / 2);                       
           
                                                 // Check if the mid element                       
                                                 // is the repeating one                       
                                                 if                                     (                                     $arr                                     [                                     $mid                                     ] !=                                     $mid                                     + 1)                       
                                                 {                       
                                                 if                                     (                                     $mid                                     > 0 &&                                     $arr                                     [                                     $mid                                     ] ==                       
                                                 $arr                                     [                                     $mid                                     - 1])                       
                                                 return                                     $mid                                     ;                       
           
                                                 // If mid element is not at                       
                                                 // its position that means                       
                                                 // the repeated element is in left                       
                                                 return                                     findRepeatingElement(                                     $arr                                     ,                                     $low                                     ,                       
                                                 $mid                                     - 1);                       
                                                 }                       
           
                                                 // If mid is at proper position                       
                                                 // then repeated one is in right.                       
                                                 return                                     findRepeatingElement(                                     $arr                                     ,                                     $mid                                     + 1,                       
                                                 $high                                     );                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (1, 2, 3, 3, 4, 5);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         $index                                     = findRepeatingElement(                                     $arr                                     , 0,                       
                                                 $n                                     - 1);                       
                         if                                     (                                     $index                                     != -1)                       
                         echo                                     $arr                                     [                                     $index                                     ];                       
           
                         // This code is contributed                       
                         // by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
                                                 // JavaScript program to find the only repeating element in an                       
                                                 // array of size n and elements from range 1 to n-1.                       
           
                                                 // Returns index of second appearance of a repeating element                       
                                                 // The function assumes that array elements are in range from                       
                                                 // 1 to n-1.                       
                                                 function                                     findRepeatingElement(arr, low, high)                       
                                                 {                       
                                   
                                                 // low = 0 , high = n-1;                       
                                                 if                                     (low > high)                                     return                                     -1;                       
           
                                                 var                                     mid = parseInt((low + high) / 2);                       
           
                                                 // Check if the mid element is the repeating one                       
                                                 if                                     (arr[mid] != mid + 1)                       
                                                 {                       
                                                 if                                     (mid > 0 && arr[mid] == arr[mid - 1])                                     return                                     mid;                       
           
                                                 // If mid element is not at its position that means                       
                                                 // the repeated element is in left                       
                                                 return                                     findRepeatingElement(arr, low, mid - 1);                       
                                                 }                       
           
                                                 // If mid is at proper position then repeated one is in                       
                                                 // right.                       
                                                 return                                     findRepeatingElement(arr, mid + 1, high);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 var                                     arr = [1, 2, 3, 3, 4, 5];                       
                                                 var                                     n = arr.length;                       
                                                 var                                     index = findRepeatingElement(arr, 0, n - 1);                       
                                                 if                                     (index != -1) document.write(arr[index]);                       
                                   
                                                 // This code is contributed by rdtank.                       
                                                 </script>                       

输出：

时间复杂性： O（对数n）本文由 萨希尔·查布拉（杀手） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章