資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究編寫一個 C++ 程式，在給定的無序整數陣列中查詢缺失的正數。
假設我們給定了一個無序整數陣列。任務是在給定陣列的範圍 [0 到 n] 內找到不存在的正整數。例如，
輸入 1 −
N = 9 arr = [0,2,5,9,1,7,4,3,6]
輸出 −
8
解釋 − 在給定的無序陣列中，“8” 是唯一缺失的正整數，因此輸出為“8”。
輸入 2 −
>N= 1 arr= [0]
輸出 −
1
解釋 − 在給定的陣列中，“1” 是唯一缺失的正整數，因此輸出為“1”。
解決此問題的方法
有幾種方法可以解決此特定問題。但是，我們可以線上性時間 O(n) 和常數空間 O(1) 內解決此問題。
由於我們知道我們的陣列大小為 n，並且它正好包含 [0 到 n] 範圍內的元素。因此，如果我們對每個元素及其索引與“n”執行 XOR 運算，那麼我們可以找到結果數字作為陣列中缺失的唯一數字。
輸入陣列大小 N，其元素在 [0 到 n] 範圍內。
一個整數函式 findMissingNumber(int arr[], int size) 以陣列及其大小作為輸入，並返回缺失的數字。
讓我們將n 作為缺失的數字來執行 XOR 運算。
遍歷所有陣列元素，並對每個陣列元素及其索引與缺失數字n執行 XOR 運算。
現在返回缺失的數字。
示例
#include<bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size){
int missing_no= size;
for(int i=0;i<size;i++){
missing_no^= i^arr[i];
}
return missing_no;
}
int main(){
int n= 6;
int arr[n]= {0,4,2,1,6,3};
cout<<findMissingNumber(arr,n)<<endl;
return 0;
}輸出
如果我們執行以上程式碼，它將列印輸出為：
5
如果我們對陣列的每個元素及其索引執行 XOR 運算，它將列印“5”，它在陣列中缺失。
更新於: 2021 年 2 月 5 日
395 次檢視
廣告