给定一个递增序列 a[] ，我们需要在递增序列中找到序列中不存在的第K个缺失连续元素。如果没有第k个缺失元素，则输出-1。
null
例如：
Input : a[] = {2, 3, 5, 9, 10}; k = 1;Output : 1Explanation: Missing Element in the increasing sequence are {1,4, 6, 7, 8}. So k-th missing elementis 1Input : a[] = {2, 3, 5, 9, 10, 11, 12}; k = 4;Output : 7Explanation: missing element in the increasing sequence are {1, 4, 6, 7, 8} so k-th missing element is 7
方法1： 开始迭代数组元素，对于每个元素，检查下一个元素是否连续，如果不连续，则取这两个元素之间的差值，检查差值是否大于或等于给定的k，然后计算ans=a[i]+计数，否则迭代下一个元素。
C++
#include <bits/stdc++.h> using namespace std; // Function to find k-th // missing element int missingK( int a[], int k, int n) { int difference = 0, ans = 0, count = k; bool flag = 0; //case when first number is not 1 if (a[0] != 1){ difference = a[0]-1; if (difference >= count) return count; count -= difference; } // iterating over the array for ( int i = 0 ; i < n - 1; i++) { difference = 0; // check if i-th and // (i + 1)-th element // are not consecutive if ((a[i] + 1) != a[i + 1]) { // save their difference difference += (a[i + 1] - a[i]) - 1; // check for difference // and given k if (difference >= count) { ans = a[i] + count; flag = 1; break ; } else count -= difference; } } // if found if (flag) return ans; else return -1; } // Driver code int main() { // Input array int a[] = {1, 5, 11, 19}; // k-th missing element // to be found in the array int k = 11; int n = sizeof (a) / sizeof (a[0]); // calling function to // find missing element int missing = missingK(a, k, n); cout << missing << endl; return 0; } |
JAVA
// Java program to check for // even or odd import java.io.*; import java.util.*; public class GFG { // Function to find k-th // missing element static int missingK( int []a, int k, int n) { int difference = 0 , ans = 0 , count = k; boolean flag = false ; //case when first number is not 1 if (a[ 0 ] != 1 ){ difference = a[ 0 ]- 1 ; if (difference >= count) return count; count -= difference; } // iterating over the array for ( int i = 0 ; i < n - 1 ; i++) { difference = 0 ; // check if i-th and // (i + 1)-th element // are not consecutive if ((a[i] + 1 ) != a[i + 1 ]) { // save their difference difference += (a[i + 1 ] - a[i]) - 1 ; // check for difference // and given k if (difference >= count) { ans = a[i] + count; flag = true ; break ; } else count -= difference; } } // if found if (flag) return ans; else return - 1 ; } // Driver code public static void main(String args[]) { // Input array int []a = { 1 , 5 , 11 , 19 }; // k-th missing element // to be found in the array int k = 11 ; int n = a.length; // calling function to // find missing element int missing = missingK(a, k, n); System.out.print(missing); } } // This code is contributed by // Manish Shaw (manishshaw1) |
Python3
# Function to find k-th # missing element def missingK(a, k, n) : difference = 0 ans = 0 count = k flag = 0 #case when first number is not 1 if a[ 0 ] ! = 1 : difference = a[ 0 ] - 1 if difference > = count: return count count - = difference # iterating over the array for i in range ( 0 , n - 1 ) : difference = 0 # check if i-th and # (i + 1)-th element # are not consecutive if ((a[i] + 1 ) ! = a[i + 1 ]) : # save their difference difference + = (a[i + 1 ] - a[i]) - 1 # check for difference # and given k if (difference > = count) : ans = a[i] + count flag = 1 break else : count - = difference # if found if (flag) : return ans else : return - 1 # Driver code # Input array a = [ 1 , 5 , 11 , 19 ] # k-th missing element # to be found in the array k = 11 n = len (a) # calling function to # find missing element missing = missingK(a, k, n) print (missing) # This code is contributed by # Manish Shaw (manishshaw1) |
C#
// C# program to check for // even or odd using System; using System.Collections.Generic; class GFG { // Function to find k-th // missing element static int missingK( int []a, int k, int n) { int difference = 0, ans = 0, count = k; bool flag = false ; //case when first number is not 1 if (a[0] != 1){ difference = a[0]-1; if (difference >= count) return count; count -= difference; } // iterating over the array for ( int i = 0 ; i < n - 1; i++) { difference = 0; // check if i-th and // (i + 1)-th element // are not consecutive if ((a[i] + 1) != a[i + 1]) { // save their difference difference += (a[i + 1] - a[i]) - 1; // check for difference // and given k if (difference >= count) { ans = a[i] + count; flag = true ; break ; } else count -= difference; } } // if found if (flag) return ans; else return -1; } // Driver code public static void Main() { // Input array int []a = {1, 5, 11, 19}; // k-th missing element // to be found in the array int k = 11; int n = a.Length; // calling function to // find missing element int missing = missingK(a, k, n); Console.Write(missing); } } // This code is contributed by // Manish Shaw (manishshaw1) |
PHP
<?php // Function to find k-th // missing element function missingK(& $a , $k , $n ) { $difference = 0; $ans = 0; $count = $k ; $flag = 0; // iterating over the array for ( $i = 0 ; $i < $n - 1; $i ++) { $difference = 0; // check if i-th and // (i + 1)-th element // are not consecutive if (( $a [ $i ] + 1) != $a [ $i + 1]) { // save their difference $difference += ( $a [ $i + 1] - $a [ $i ]) - 1; // check for difference // and given k if ( $difference >= $count ) { $ans = $a [ $i ] + $count ; $flag = 1; break ; } else $count -= $difference ; } } // if found if ( $flag ) return $ans ; else return -1; } // Driver Code // Input array $a = array (1, 5, 11, 19); // k-th missing element // to be found in the array $k = 11; $n = count ( $a ); // calling function to // find missing element $missing = missingK( $a , $k , $n ); echo $missing ; // This code is contributed by Manish Shaw // (manishshaw1) ?> |
Javascript
<script> // Javascript program to check for // even or odd // Function to find k-th // missing element function missingK(a, k, n) { let difference = 0, ans = 0, count = k; let flag = false ; //case when first number is not 1 if (a[0] != 1){ difference = a[0]-1; if (difference >= count){ return count; } count -= difference; } // iterating over the array for (let i = 0 ; i < n - 1; i++) { difference = 0; // Check if i-th and // (i + 1)-th element // are not consecutive if ((a[i] + 1) != a[i + 1]) { // Save their difference difference += (a[i + 1] - a[i]) - 1; // Check for difference // and given k if (difference >= count) { ans = a[i] + count; flag = true ; break ; } else count -= difference; } } // If found if (flag) return ans; else return -1; } // Driver code // Input array let a = [ 1, 5, 11, 19 ]; // k-th missing element // to be found in the array let k = 11; let n = a.length; // Calling function to // find missing element let missing = missingK(a, k, n); document.write(missing); // This code is contributed by suresh07 </script> |
输出
14
时间复杂性： O（n），其中n是数组中的元素数。
方法2：
应用二进制搜索。由于数组被排序，我们可以在任何给定的索引中找到arr[index]–（index+1）缺少多少数字。我们将利用这些知识，应用二进制搜索来缩小搜索范围，以找到更容易获取缺失数字的索引。
以下是上述方法的实施情况：
C++
// CPP program for above approach #include <iostream> #include <bits/stdc++.h> using namespace std; // Function to find // kth missing number int missingK(vector< int >& arr, int k) { int n = arr.size(); int l = 0, u = n - 1, mid; while (l <= u) { mid = (l + u)/2; int numbers_less_than_mid = arr[mid] - (mid + 1); // If the total missing number // count is equal to k we can iterate // backwards for the first missing number // and that will be the answer. if (numbers_less_than_mid == k) { // To further optimize we check // if the previous element's // missing number count is equal // to k. Eg: arr = [4,5,6,7,8] // If you observe in the example array, // the total count of missing numbers for all // the indices are same, and we are // aiming to narrow down the // search window and achieve O(logn) // time complexity which // otherwise would've been O(n). if (mid > 0 && (arr[mid - 1] - (mid)) == k) { u = mid - 1; continue ; } // Else we return arr[mid] - 1. return arr[mid]-1; } // Here we appropriately // narrow down the search window. if (numbers_less_than_mid < k) { l = mid + 1; } else if (k < numbers_less_than_mid) { u = mid - 1; } } // In case the upper limit is -ve // it means the missing number set // is 1,2,..,k and hence we directly return k. if (u < 0) return k; // Else we find the residual count // of numbers which we'd then add to // arr[u] and get the missing kth number. int less = arr[u] - (u + 1); k -= less; // Return arr[u] + k return arr[u] + k; } // Driver Code int main() { vector< int > arr = {2,3,4,7,11}; int k = 5; // Function Call cout << "Missing kth number = " << missingK(arr, k)<<endl; return 0; } |
JAVA
// Java program for above approach public class GFG { // Function to find // kth missing number static int missingK( int [] arr, int k) { int n = arr.length; int l = 0 , u = n - 1 , mid; while (l <= u) { mid = (l + u)/ 2 ; int numbers_less_than_mid = arr[mid] - (mid + 1 ); // If the total missing number // count is equal to k we can iterate // backwards for the first missing number // and that will be the answer. if (numbers_less_than_mid == k) { // To further optimize we check // if the previous element's // missing number count is equal // to k. Eg: arr = [4,5,6,7,8] // If you observe in the example array, // the total count of missing numbers for all // the indices are same, and we are // aiming to narrow down the // search window and achieve O(logn) // time complexity which // otherwise would've been O(n). if (mid > 0 && (arr[mid - 1 ] - (mid)) == k) { u = mid - 1 ; continue ; } // Else we return arr[mid] - 1. return arr[mid] - 1 ; } // Here we appropriately // narrow down the search window. if (numbers_less_than_mid < k) { l = mid + 1 ; } else if (k < numbers_less_than_mid) { u = mid - 1 ; } } // In case the upper limit is -ve // it means the missing number set // is 1,2,..,k and hence we directly return k. if (u < 0 ) return k; // Else we find the residual count // of numbers which we'd then add to // arr[u] and get the missing kth number. int less = arr[u] - (u + 1 ); k -= less; // Return arr[u] + k return arr[u] + k; } // Driver code public static void main(String[] args) { int [] arr = { 2 , 3 , 4 , 7 , 11 }; int k = 5 ; // Function Call System.out.println( "Missing kth number = " + missingK(arr, k)); } } // This code is contributed by divyesh072019. |
Python3
# Python3 program for above approach # Function to find # kth missing number def missingK(arr, k): n = len (arr) l = 0 u = n - 1 mid = 0 while (l < = u): mid = (l + u) / / 2 ; numbers_less_than_mid = arr[mid] - (mid + 1 ); # If the total missing number # count is equal to k we can iterate # backwards for the first missing number # and that will be the answer. if (numbers_less_than_mid = = k): # To further optimize we check # if the previous element's # missing number count is equal # to k. Eg: arr = [4,5,6,7,8] # If you observe in the example array, # the total count of missing numbers for all # the indices are same, and we are # aiming to narrow down the # search window and achieve O(logn) # time complexity which # otherwise would've been O(n). if (mid > 0 and (arr[mid - 1 ] - (mid)) = = k): u = mid - 1 ; continue ; # Else we return arr[mid] - 1. return arr[mid] - 1 ; # Here we appropriately # narrow down the search window. if (numbers_less_than_mid < k): l = mid + 1 ; elif (k < numbers_less_than_mid): u = mid - 1 ; # In case the upper limit is -ve # it means the missing number set # is 1,2,..,k and hence we directly return k. if (u < 0 ): return k; # Else we find the residual count # of numbers which we'd then add to # arr[u] and get the missing kth number. less = arr[u] - (u + 1 ); k - = less; # Return arr[u] + k return arr[u] + k; # Driver Code if __name__ = = '__main__' : arr = [ 2 , 3 , 4 , 7 , 11 ]; k = 5 ; # Function Call print ( "Missing kth number = " + str (missingK(arr, k))) # This code is contributed by rutvik_56. |
C#
// C# program for above approach using System; class GFG { // Function to find // kth missing number static int missingK( int [] arr, int k) { int n = arr.Length; int l = 0, u = n - 1, mid; while (l <= u) { mid = (l + u)/2; int numbers_less_than_mid = arr[mid] - (mid + 1); // If the total missing number // count is equal to k we can iterate // backwards for the first missing number // and that will be the answer. if (numbers_less_than_mid == k) { // To further optimize we check // if the previous element's // missing number count is equal // to k. Eg: arr = [4,5,6,7,8] // If you observe in the example array, // the total count of missing numbers for all // the indices are same, and we are // aiming to narrow down the // search window and achieve O(logn) // time complexity which // otherwise would've been O(n). if (mid > 0 && (arr[mid - 1] - (mid)) == k) { u = mid - 1; continue ; } // Else we return arr[mid] - 1. return arr[mid] - 1; } // Here we appropriately // narrow down the search window. if (numbers_less_than_mid < k) { l = mid + 1; } else if (k < numbers_less_than_mid) { u = mid - 1; } } // In case the upper limit is -ve // it means the missing number set // is 1,2,..,k and hence we directly return k. if (u < 0) return k; // Else we find the residual count // of numbers which we'd then add to // arr[u] and get the missing kth number. int less = arr[u] - (u + 1); k -= less; // Return arr[u] + k return arr[u] + k; } // Driver code static void Main() { int [] arr = {2,3,4,7,11}; int k = 5; // Function Call Console.WriteLine( "Missing kth number = " + missingK(arr, k)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // JavaScript program for above approach // Function to find // kth missing number function missingK(arr, k) { var n = arr.length; var l = 0, u = n - 1, mid; while (l <= u) { mid = (l + u)/2; var numbers_less_than_mid = arr[mid] - (mid + 1); // If the total missing number // count is equal to k we can iterate // backwards for the first missing number // and that will be the answer. if (numbers_less_than_mid == k) { // To further optimize we check // if the previous element's // missing number count is equal // to k. Eg: arr = [4,5,6,7,8] // If you observe in the example array, // the total count of missing numbers for all // the indices are same, and we are // aiming to narrow down the // search window and achieve O(logn) // time complexity which // otherwise would've been O(n). if (mid > 0 && (arr[mid - 1] - (mid)) == k) { u = mid - 1; continue ; } // Else we return arr[mid] - 1. return arr[mid] - 1; } // Here we appropriately // narrow down the search window. if (numbers_less_than_mid < k) { l = mid + 1; } else if (k < numbers_less_than_mid) { u = mid - 1; } } // In case the upper limit is -ve // it means the missing number set // is 1,2,..,k and hence we directly return k. if (u < 0) return k; // Else we find the residual count // of numbers which we'd then add to // arr[u] and get the missing kth number. var less = arr[u] - (u + 1); k -= less; // Return arr[u] + k return arr[u] + k; } // Driver code var arr = [2,3,4,7,11]; var k = 5; // Function Call document.write( "Missing kth number = " + missingK(arr, k)); // This code is contributed by shivanisinghss2110 </script> |
输出
Missing kth number = 9
时间复杂性： O（logn），其中n是数组中的元素数。
方法3（使用地图）： 我们将遍历数组，并将每个元素标记为地图中访问的元素，我们还将跟踪存在的最小和最大元素，以便我们知道给定特定输入的下限和上限。然后我们从下限开始循环到上限，并维护一个计数变量。一旦我们发现一个元素不在地图中，我们就增加计数，直到计数等于k。
C++14
#include <iostream> #include <unordered_map> using namespace std; int solve( int arr[] , int k , int n) { unordered_map< int , int > umap; int mins = 99999; int maxs = -99999; for ( int i=0 ; i<n ; i++) { umap[arr[i]] = 1; //mark each element of array in map if (mins > arr[i]) mins = arr[i]; //keeping track of minimum element if (maxs < arr[i]) maxs = arr[i]; //keeping track of maximum element i.e. upper bound } int counts = 0; //iterate from lower to upper bound for ( int i=mins ; i<=maxs ; i++) { if (umap[i] == 0) counts++; if (counts == k) return i; } return -1; } int main() { int arr[] = {2, 3, 5, 9, 10, 11, 12} ; int k = 4; cout << solve(arr , k , 7) ; //(array , k , size of array) return 0; } |
JAVA
// Java approach // Importing HashMap class import java.util.HashMap; class GFG { public static int solve( int arr[] , int k , int n) { HashMap<Integer, Integer> umap = new HashMap<Integer, Integer>(); int mins = 99999 ; int maxs = - 99999 ; for ( int i = 0 ; i < n; i++) { umap.put(arr[i], 1 ); // mark each element of array in map if (mins > arr[i]) mins = arr[i]; // keeping track of minimum element if (maxs < arr[i]) maxs = arr[i]; // keeping track of maximum element i.e. upper bound } int counts = 0 ; // iterate from lower to upper bound for ( int i = mins; i <= maxs; i++) { if (umap.get(i) == null ) counts++; if (counts == k) return i; } return - 1 ; } public static void main (String[] args) { int arr[] = { 2 , 3 , 5 , 9 , 10 , 11 , 12 } ; int k = 4 ; System.out.println(solve(arr , k , 7 )); //(array , k , size of array) } } // This code is contributed by Shubham Singh |
Python3
# Python approach def solve( arr , k , n): umap = {} mins = 99999 maxs = - 99999 for i in range (n): umap[arr[i]] = 1 #mark each element of array in map if (mins > arr[i]): mins = arr[i] #keeping track of minimum element if (maxs < arr[i]): maxs = arr[i] #keeping track of maximum element i.e. upper bound counts = 0 # iterate from lower to upper bound for i in range (mins, maxs + 1 ): if (i not in umap): counts + = 1 if (counts = = k): return i return - 1 arr = [ 2 , 3 , 5 , 9 , 10 , 11 , 12 ] k = 4 print (solve(arr , k , 7 )) #(array , k , size of array) # This code is contributed # by Shubham Singh |
输出
8
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
