您将得到一个由N个整数组成的排序数组，从1到N，其中一个数字缺失。查找缺失的数字预期的时间复杂度 O（logn） 例如：
null
Input :ar[] = {1, 3, 4, 5}Output : 2Input : ar[] = {1, 2, 3, 4, 5, 7, 8}Output : 6
A. 简单解决方案 就是线性遍历给定的数组。找到当前元素不比上一个元素多的点。 一 有效解决方案 就是使用 二进制搜索 .我们使用索引搜索缺少的元素，并修改二进制搜索。如果元素位于中间！=索引+1，这是第一个缺少的元素，然后中间+1是缺少的元素。否则，如果这不是第一个缺少的元素，而是ar[mid]！=在左半部分进行中+1搜索。否则在右半部分搜索，如果左>右，则不缺少任何元素。
C++
// CPP program to find the only missing element. #include <iostream> using namespace std; int findmissing( int ar[], int N) { int l = 0, r = N - 1; while (l <= r) { int mid = (l + r) / 2; // If this is the first element // which is not index + 1, then // missing element is mid+1 if (ar[mid] != mid + 1 && ar[mid - 1] == mid) return mid + 1; // if this is not the first missing // element search in left side if (ar[mid] != mid + 1) r = mid - 1; // if it follows index+1 property then // search in right side else l = mid + 1; } // if no element is missing return -1; } // Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 7, 8}; int N = sizeof (arr)/ sizeof (arr[0]); cout << findmissing(arr, N); return 0; } |
JAVA
// Java program to find // the only missing element. class GFG { static int findmissing( int [] ar, int N) { int l = 0 , r = N - 1 ; while (l <= r) { int mid = (l + r) / 2 ; // If this is the first element // which is not index + 1, then // missing element is mid+1 if (ar[mid] != mid + 1 && ar[mid - 1 ] == mid) return (mid + 1 ); // if this is not the first // missing element search // in left side if (ar[mid] != mid + 1 ) r = mid - 1 ; // if it follows index+1 // property then search // in right side else l = mid + 1 ; } // if no element is missing return - 1 ; } // Driver code public static void main(String [] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 7 , 8 }; int N = arr.length; System.out.println(findmissing(arr, N)); } } // This code is contributed // by Shivi_Aggarwal |
Python3
# PYTHON 3 program to find # the only missing element. def findmissing(ar, N): l = 0 r = N - 1 while (l < = r): mid = (l + r) / 2 mid = int (mid) # If this is the first element # which is not index + 1, then # missing element is mid+1 if (ar[mid] ! = mid + 1 and ar[mid - 1 ] = = mid): return (mid + 1 ) # if this is not the first # missing element search # in left side elif (ar[mid] ! = mid + 1 ): r = mid - 1 # if it follows index+1 # property then search # in right side else : l = mid + 1 # if no element is missing return ( - 1 ) def main(): ar = [ 1 , 2 , 3 , 4 , 5 , 7 , 8 ] N = len (ar) res = findmissing(ar, N) print (res) if __name__ = = "__main__" : main() # This code is contributed # by Shivi_Aggarwal |
C#
// C# program to find // the only missing element. using System; class GFG { static int findmissing( int []ar, int N) { int l = 0, r = N - 1; while (l <= r) { int mid = (l + r) / 2; // If this is the first element // which is not index + 1, then // missing element is mid+1 if (ar[mid] != mid + 1 && ar[mid - 1] == mid) return (mid + 1); // if this is not the first // missing element search // in left side if (ar[mid] != mid + 1) r = mid - 1; // if it follows index+1 // property then search // in right side else l = mid + 1; } // if no element is missing return -1; } // Driver code public static void Main() { int []arr = {1, 2, 3, 4, 5, 7, 8}; int N = arr.Length; Console.WriteLine(findmissing(arr, N)); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP program to find // the only missing element. function findmissing(& $ar , $N ) { $r = $N - 1; $l = 0; while ( $l <= $r ) { $mid = ( $l + $r ) / 2; // If this is the first element // which is not index + 1, then // missing element is mid+1 if ( $ar [ $mid ] != $mid + 1 && $ar [ $mid - 1] == $mid ) return ( $mid + 1); // if this is not the first // missing element search // in left side if ( $ar [ $mid ] != $mid + 1) $r = $mid - 1; // if it follows index+1 // property then search // in right side else $l = $mid + 1; } // if no element is missing return (-1); } // Driver Code $ar = array (1, 2, 3, 4, 5, 7, 8); $N = sizeof( $ar ); echo (findmissing( $ar , $N )); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // JavaScript program to find the only missing element. function findmissing(ar, N) { var l = 0, r = N - 1; while (l <= r) { var mid = parseInt((l + r) / 2); // If this is the first element // which is not index + 1, then // missing element is mid+1 if (ar[mid] != mid + 1 && ar[mid - 1] == mid) return mid + 1; // if this is not the first missing // element search in left side if (ar[mid] != mid + 1) r = mid - 1; // if it follows index+1 property then // search in right side else l = mid + 1; } // if no element is missing return -1; } // Driver code var arr = [1, 2, 3, 4, 5, 7, 8]; var N = arr.length; document.write(findmissing(arr, N)); </script> |
输出：
6
时间复杂性： O（对数n） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
