在排序的数组中查找缺少的数字-yiteyi-C++库

给定一个n-1个整数的列表，这些整数在1到n的范围内。列表中没有重复项。列表中缺少一个整数。编写一个高效的代码来查找缺少的整数。 例如：

null

Input : arr[] = [1, 2, 3, 4, 6, 7, 8]Output : 5Input : arr[] = [1, 2, 3, 4, 5, 6, 8, 9]Output : 7

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

一 简单解决方案 就是应用讨论过的方法在未排序的数组中查找缺少的元素该解的时间复杂度为O（n）。一 有效解决方案 基于我们在二进制搜索中看到的分治算法，这个解决方案背后的概念是，出现在缺失元素之前的元素将有ar[i]-i=1，出现在缺失元素之后的元素将有ar[i]-i=2。此解决方案的时间复杂度为O（logn）

C++

                         // A binary search based program to find the                       
                         // only missing number in a sorted array of                       
                         // distinct elements within limited range.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     search(                                     int                                     ar[],                                     int                                     size)                       
                         {                       
                                                 int                                     a = 0, b = size - 1;                       
                                                 int                                     mid;                       
                                                 while                                     ((b - a) > 1) {                       
                                                 mid = (a + b) / 2;                       
                                                 if                                     ((ar[a] - a) != (ar[mid] - mid))                       
                                                 b = mid;                       
                                                 else                                     if                                     ((ar[b] - b) != (ar[mid] - mid))                       
                                                 a = mid;                       
                                                 }                       
                                                 return                                     (ar[a] + 1);                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     ar[] = { 1, 2, 3, 4, 5, 6, 8 };                       
                                                 int                                     size =                                     sizeof                                     (ar) /                                     sizeof                                     (ar[0]);                       
                                                 cout <<                                     "Missing number:"                                     << search(ar, size);                       
                         }                       

JAVA

                         // A binary search based program                       
                         // to find the only missing number                       
                         // in a sorted array of distinct                       
                         // elements within limited range.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     search(                                     int                                     ar[],                       
                                                 int                                     size)                       
                         {                       
                                                 int                                     a =                                     0                                     , b = size -                                     1                                     ;                       
                                                 int                                     mid =                                     0                                     ;                       
                                                 while                                     ((b - a) >                                     1                                     )                       
                                                 {                       
                                                 mid = (a + b) /                                     2                                     ;                       
                                                 if                                     ((ar[a] - a) != (ar[mid] - mid))                       
                                                 b = mid;                       
                                                 else                                     if                                     ((ar[b] - b) != (ar[mid] - mid))                       
                                                 a = mid;                       
                                                 }                       
                                                 return                                     (ar[a] +                                     1                                     );                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     ar[] = {                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     8                                     };                       
                                                 int                                     size = ar.length;                       
                                                 System.out.println(                                     "Missing number: "                                     +                       
                                                 search(ar, size));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by inder_verma.                       

Python3

                         # A binary search based program to find                       
                         # the only missing number in a sorted                       
                         # in a sorted array of distinct elements                       
                         # within limited range                       
                         def                                     search(ar, size):                       
                                                 a                                     =                                     0                       
                                                 b                                     =                                     size                                     -                                     1                       
                                                 mid                                     =                                     0                       
                                                 while                                     b > a                                     +                                     1                                     :                       
                                                 mid                                     =                                     (a                                     +                                     b)                                     /                                     /                                     2                       
                                                 if                                     (ar[a]                                     -                                     a) !                                     =                                     (ar[mid]                                     -                                     mid):                       
                                                 b                                     =                                     mid                       
                                                 elif                                     (ar[b]                                     -                                     b) !                                     =                                     (ar[mid]                                     -                                     mid):                       
                                                 a                                     =                                     mid                       
                                                 return                                     ar[a]                                     +                                     1                       
           
                         # Driver Code                       
                         a                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     8                                     ]                       
                         n                                     =                                     len                                     (a)                       
           
                         print                                     (                                     "Missing number:"                                     , search(a, n))                       
           
                         # This code is contributed                       
                         # by Mohit Kumar                       

C#

                         // A binary search based program                       
                         // to find the only missing number                       
                         // in a sorted array of distinct                       
                         // elements within limited range.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     search(                                     int                                     []ar,                       
                                                 int                                     size)                       
                         {                       
                                                 int                                     a = 0, b = size - 1;                       
                                                 int                                     mid = 0;                       
                                                 while                                     ((b - a) > 1)                       
                                                 {                       
                                                 mid = (a + b) / 2;                       
                                                 if                                     ((ar[a] - a) != (ar[mid] - mid))                       
                                                 b = mid;                       
                                                 else                                     if                                     ((ar[b] - b) != (ar[mid] - mid))                       
                                                 a = mid;                       
                                                 }                       
                                                 return                                     (ar[a] + 1);                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main (String []args)                       
                         {                       
                                                 int                                     []ar = { 1, 2, 3, 4, 5, 6, 8 };                       
                                                 int                                     size = ar.Length;                       
                                                 Console.WriteLine(                                     "Missing number: "                                     +                       
                                                 search(ar, size));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Arnab Kundu                       

PHP

                         <?php                       
                         // A binary search based program to find the                       
                         // only missing number in a sorted array of                       
                         // distinct elements within limited range.                       
           
                         function                                     search(                                     $ar                                     ,                                     $size                                     )                       
                         {                       
                                                 $a                                     = 0;                       
                                                 $b                                     =                                     $size                                     - 1;                       
                                                 $mid                                     ;                       
                                                 while                                     ((                                     $b                                     -                                     $a                                     ) > 1)                       
                                                 {                       
                                                 $mid                                     = (int)((                                     $a                                     +                                     $b                                     ) / 2);                       
                                                 if                                     ((                                     $ar                                     [                                     $a                                     ] -                                     $a                                     ) != (                                     $ar                                     [                                     $mid                                     ] -                       
                                                 $mid                                     ))                       
                                                 $b                                     =                                     $mid                                     ;                       
                                                 else                                     if                                     ((                                     $ar                                     [                                     $b                                     ] -                                     $b                                     ) != (                                     $ar                                     [                                     $mid                                     ] -                       
                                                 $mid                                     ))                       
                                                 $a                                     =                                     $mid                                     ;                       
                                                 }                       
                                                 return                                     (                                     $ar                                     [                                     $a                                     ] + 1);                       
                         }                       
           
                         // Driver Code                       
                         $ar                                     =                                     array                                     (1, 2, 3, 4, 5, 6, 8 );                       
                         $size                                     = sizeof(                                     $ar                                     );                       
                         echo                                     "Missing number: "                                     ,                       
                                                 search(                                     $ar                                     ,                                     $size                                     );                       
           
                         // This code is contributed by ajit.                       
                         ?>                       

Javascript

                         <script>                       
                         // A binary search based program                       
                         // to find the only missing number                       
                         // in a sorted array of distinct                       
                         // elements within limited range.                       
           
                         function                                     findMissing(arr) {                       
                                                 var                                     low = 0;                       
                                                 var                                     high = arr.length;                       
                                                 while                                     (low <= high) {                       
                                                 var                                     mid = Math.floor((low+high)/2);                       
                                                 if                                     ((arr[mid]-mid === 1) && (arr[mid+1]-(mid+1) === 2))                                     return                                     arr[mid]+1;                       
                                                 if                                     (arr[mid]-mid === 1) {                       
                                                 low = mid+1;                       
                                                 }                                     else                                     {                       
                                                 high = mid-1;                       
                                                 }                       
                                                 }                       
                                                 return                                     -1;                       
                         }                       
           
                         // Driver Code                       
           
                         let ar = [1, 2, 3, 4, 5, 6, 8];                       
                         document.write(                                     "Missing number: "                                     +findMissing(ar));                       
           
                         // This code is contributed by mohit kumar 29.                       
                         </script>                       

输出：

Missing number: 7

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

THE END

技术文章