首頁猿問在數(shù)字?jǐn)?shù)組中查找缺失數(shù)字的最快方法

在數(shù)字?jǐn)?shù)組中查找缺失數(shù)字的最快方法

Java 算法

月關(guān)寶盒 2019-11-05 16:23:20

我有一個從1到100（包括兩端）的數(shù)字?jǐn)?shù)組。數(shù)組的大小為100。將數(shù)字隨機(jī)添加到數(shù)組中，但是數(shù)組中有一個隨機(jī)的空插槽。找到該插槽的最快方法是什么，以及應(yīng)該在插槽中放入多少數(shù)字？最好使用Java解決方案。

查看完整描述

3 回答

慕神8447489

TA貢獻(xiàn)1780條經(jīng)驗獲得超1個贊

我們可以使用比求和更安全的XOR操作，因為在編程語言中，如果給定的輸入很大，則可能會溢出并給出錯誤的答案。

在尋求解決方案之前，請知道A xor A = 0。因此，如果我們對兩個相同的數(shù)字進(jìn)行XOR運算，則該值為0。

現(xiàn)在，對數(shù)組中存在的元素進(jìn)行XORing [1..n]會取消相同的數(shù)字。因此，最后我們將得到缺少的號碼。

// Assuming that the array contains 99 distinct integers between 1..99

// and empty slot value is zero

int XOR = 0;

for(int i=0; i<100; i++) {

if (ARRAY[i] != 0) // remove this condition keeping the body if no zero slot

XOR ^= ARRAY[i];

XOR ^= (i + 1);

}

return XOR;

//return XOR ^ ARRAY.length + 1; if your array doesn't have empty zero slot.

反對回復(fù) 2019-11-05

3 回答
0 關(guān)注
1261 瀏覽

關(guān)注

添加回答

舉報

0/150

提交

取消

使用 Ctrl+D 可將網(wǎng)站添加到書簽

微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號

第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

熱搜

最近搜索清空

在數(shù)字?jǐn)?shù)組中查找缺失數(shù)字的最快方法

在數(shù)字?jǐn)?shù)組中查找缺失數(shù)字的最快方法

3 回答

添加回答