排序数组中的第k个缺失元素
原文： 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] + count，否则迭代下一个元素。
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;
// 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 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
# 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#
// 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
// 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是数组中元素的数量。
版权属于：月萌API www.moonapi.com，转载请注明出处
