資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律使用 C++ 查詢排序陣列中唯一缺失的數字
在這個問題中，我們得到一個大小為 N 的陣列 arr[]，其中包含從 1 到 N 的值，陣列中缺少一個值。我們的任務是查詢排序陣列中唯一缺失的數字。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {1, 2, 3, 5, 6, 7}輸出
4
解決方案方法
解決此問題的一個簡單方法是線性遍歷排序陣列。然後使用 arr[i] = (i + 1) 的事實來檢查缺失的值。
示例 1
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] != (i+1))
return (i+1);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
return 0;
}輸出
The missing value from the array is 5
解決此問題的另一種方法是使用二分查詢並檢查中間的值。如果中間的值是 mid+1 並且 (mid - 1) 處的值是 (mid)，那麼我們將遍歷左子陣列，反之亦然。
示例 2
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
int s = 0, e = N - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
return (mid + 1);
if (arr[mid] != (mid + 1))
e = (mid - 1);
else
s = (mid + 1);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
return 0;
}輸出
The missing value from the array is 5
更新於: 2022年2月11日
1K+ 次瀏覽
廣告