資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用C++查詢範圍內缺失的一個數字
在這個問題中，我們得到一個大小為n的陣列arr[]。我們的任務是查詢範圍內缺失的一個數字。
該陣列包含從最小值到（最小值 + n）的所有值。範圍內的一個元素缺失於陣列中。我們需要找到這個缺失的值。
讓我們來看一個例子來理解這個問題：
輸入
arr[] = {4, 8, 5, 7}輸出
6
解決方案方法
解決這個問題的一個簡單方法是透過排序陣列並找到從最小值開始的範圍內第一個不在陣列中但存在於範圍內的元素來搜尋缺失的元素。
這種解決方案是一種簡單的方法，它將在O(n log n)的時間複雜度內解決問題。
另一種以更短時間解決問題的方法是使用陣列的值和範圍的XOR。我們將找到範圍內所有值的XOR，以及陣列中所有值的XOR。這兩個值的XOR將是我們的缺失值。
示例
程式說明了我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
int findMissingNumArr(int arr[], int n){
int arrMin = *min_element(arr, arr+n);
int numXor = 0;
int rangeXor = arrMin;
for (int i = 0; i < n; i++) {
numXor ^= arr[i];
arrMin++;
rangeXor ^= arrMin;
}
return numXor ^ rangeXor;
}
int main(){
int arr[] = { 5, 7, 4, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value in the array is "<<findMissingNumArr(arr, n);
return 0;
}輸出
The missing value in the array is 6
更新於：2022年2月11日
427 次瀏覽
廣告