資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究編寫一個Java程式，在一個給定的無序整數陣列中找到缺失的正數。
假設我們給定一個無序整數陣列。任務是在[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'進行異或運算，那麼我們可以找到缺失的唯一數字。
輸入陣列大小N，元素範圍為[0到n]。
整數函式findMissingNumber(int arr[], int size)接收一個數組及其大小作為輸入，並返回缺失的數字。
讓我們用n作為缺失的數字來執行異或運算。
迭代所有陣列元素，並對每個陣列元素及其索引與缺失數字n執行異或運算。
現在返回缺失的數字。
示例
public class Solution {
public static 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;
}
public static void main(String[] args){
int arr[] = {0,4,2,1,6,3};
int n = arr.length;
int a=findMissingNumber(arr, n);
System.out.println(a);
}
}輸出
執行以上程式碼將生成以下輸出：
5
在給定的陣列{0,4,2,1,6,3}中，缺失的是'5'，因此我們將返回5。
更新於：2021年2月5日
500 次瀏覽
廣告