# 排序數組中的第 k 個缺失元素 > 原文： [https://www.geeksforgeeks.org/k-th-missing-element-in-sorted-array/](https://www.geeksforgeeks.org/k-th-missing-element-in-sorted-array/) 給定一個遞增的序列 **a []** ，我們需要在遞增的序列中找到第 K 個缺失的連續元素，該元素在序列中不存在。 如果沒有第 k 個缺失元素，則輸出-1。 **示例**： ``` Input : a[] = {2, 3, 5, 9, 10}; k = 1; Output : 4 Explanation: Missing Element in the increasing sequence are {4, 6, 7, 8}. So k-th missing element is 4 Input : a[] = {2, 3, 5, 9, 10, 11, 12}; k = 4; Output : 8 Explanation: missing element in the increasing sequence are {4, 6, 7, 8} so k-th missing element is 8 ``` **方法**：開始遍歷數組元素，并對每個元素檢查下一個元素是否連續，如果不連續，則取這兩個元素之間的差，并檢查差值是否大于或等于給定的 k ，然后計算 ans = a [i] +計數，否則迭代下一個元素。 ## C++ ```cpp #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; ????// interating 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 // 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; ????????// interating 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 ```py # Function to find k-th? # missing element def missingK(a, k, n) : ????difference = 0 ????ans = 0 ????count = k ????flag = 0 ????# interating 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# ```cs // 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; ????????// interating 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 <?php // Function to find k-th? // missing element function missingK(&$a, $k, $n) { ????$difference = 0; ????$ans = 0; ????$count = $k; ????$flag = 0; ????// interating 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) ?> ``` **輸出**： ``` 14 ``` **時間復雜度**：`O(n)`，其中 n 是數組中元素的數量。 * * * * * *