資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中排序陣列中的缺失元素
假設我們有一個包含唯一數字的排序陣列 A，我們需要找到從陣列最左側數字開始的第 K 個缺失數字。例如，如果陣列為 [4,7,9,10]，並且 k = 1，則該元素將為 5。
為了解決這個問題，我們將遵循以下步驟：
n := 陣列的大小，設定 low := 0 和 high := n – 1
如果 nums[n - 1] – nums[0] + 1 – n < k，則
返回 nums[n - 1] + (k – (nums[n - 1] – nums[0] + 1 – n))
當 low < high – 1
mid := low + (high - low)/2
present := mid – low + 1
absent := nums[mid] – nums[low] + 1 – present
如果 absent >= k，則 high := mid，否則將 k 減去 absent，low := mid
返回 nums[low] + k
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int n = nums.size();
int low = 0;
int high = n - 1;
if(nums[n - 1] - nums[0] + 1 - n < k) return nums[n - 1] + (k
- ( nums[n - 1] - nums[0] + 1 - n)) ;
while(low < high - 1){
int mid = low + (high - low) / 2;
int present = mid - low + 1;
int absent = nums[mid] - nums[low] + 1 - present;
if(absent >= k){
high = mid;
}else{
k -= absent;
low = mid;
}
}
return nums[low] + k;
}
};
main(){
vector<int> v = {4,7,9,10};
Solution ob;
cout << (ob.missingElement(v, 1));
}輸入
[4,7,9,10] 1
輸出
5
更新於: 2020-04-30
407 次檢視
廣告