自從我討論任何編碼或算法面試問題以來已經(jīng)有很長時(shí)間了，因此我想重新考慮一種最流行的基于數(shù)組的編碼問題，即在給定數(shù)組中查找缺失的數(shù)字。 在進(jìn)行編程工作面試之前，您可能已經(jīng)聽說過或看到過此問題，但是面試官通常會(huì)使用許多不同的版本來提高難度，以使候選人感到困惑并進(jìn)一步測試其適應(yīng)頻繁變化的能力。 過去，我已經(jīng)演示了如何使用BitSet在Java中的未排序整數(shù)數(shù)組上以及在排序數(shù)組中查找缺失的數(shù)字 （請參閱此處 ），但是，只有一個(gè)缺失的數(shù)字并且沒有任何重復(fù)。

這使問題有些容易，但是如果面試官告訴您數(shù)組包含重復(fù)項(xiàng)并且缺少多個(gè)數(shù)字，您該怎么辦？ 好吧，這就是我們將在本文中討論的內(nèi)容，但是在此之前，讓我們正確地獲取問題說明。

1.問題陳述：

您給定了一個(gè)大小為N的整數(shù)數(shù)組。該數(shù)組包含從1到N-1的數(shù)字，但是在包含重復(fù)項(xiàng)的數(shù)組中缺少幾個(gè)數(shù)字。 編寫一個(gè)Java程序以打印序列中缺少的數(shù)字。

例如，如果給定數(shù)組為
{1，1，2，3，5，5，7，9，9，9}那么它的長度
10，其中包含1到9之間的數(shù)字。在這種情況下，缺少的數(shù)字是4、6和8。

2.解決方案：

當(dāng)你看到的問題是找到陣列失蹤人數(shù) ，你可能會(huì)認(rèn)為我們前面的解決方案計(jì)算所有數(shù)字的總和 ，并從預(yù)期的總和扣除它來尋找失蹤的數(shù)字，但不幸的是不會(huì)在這種情況下工作，因?yàn)楦嗳鄙僖粋€(gè)數(shù)字 ，并且其中包含重復(fù)項(xiàng)。

在這種情況下，我們需要使用其他方法，例如您在學(xué)校中看到的點(diǎn)名通話。

老師有一個(gè)列出所有學(xué)生姓名的登記冊，他在列表中瀏覽并用紅色標(biāo)記缺席。 我們可以使用相同的方法來查找列表中所有缺少的數(shù)字。

我們可以將數(shù)組用作寄存器，并將索引用作數(shù)字名稱。 我們遍歷給定的數(shù)組，并通過存儲(chǔ)它們各自的索引之一來標(biāo)記所有存在的數(shù)字。 例如，如果給定數(shù)組中的第一個(gè)數(shù)字為5（由于未對數(shù)組進(jìn)行排序），則我們將1存儲(chǔ)在索引5中，例如register[5] = 1

給定所有數(shù)字后，就可以遍歷寄存器數(shù)組并打印所有值為零的索引。 這些人缺席或缺席。

該解決方案對于重復(fù)項(xiàng)也是安全的，因?yàn)槿绻粋€(gè)數(shù)字出現(xiàn)一次或兩次，我們只需將1存儲(chǔ)在相應(yīng)的索引中即可。

3.代碼：

現(xiàn)在，我們知道如何解決帶有重復(fù)項(xiàng)的未排序整數(shù)數(shù)組中的數(shù)字遺漏的問題，是時(shí)候?qū)⒃摻鉀Q方案變成代碼并運(yùn)行Java程序了。

/** Java Program to find missing numbers in an integer* array with duplicates. Array may contains more* than one duplicates.* * input: {1, 1, 2, 3, 5, 5, 7, 9, 9, 9};* output: 4, 6, 8*/ public class Hello {public static void main(String[] args) {// given inputint[] input = { 1, 1, 2, 3, 5, 5, 7, 9, 9, 9 };// let's create another array with same length// by default all index will contain zero// default value for int variableint[] register = new int[input.length];// now let's iterate over given array to// mark all present numbers in our register// arrayfor (int i : input) {register[i] = 1;}// now, let's print all the absenteesSystem.out.println("missing numbers in given array");for (int i = 1; i < register.length; i++) {if (register[i] == 0) {System.out.println(i);}}}}Output missing numbers in given array 4 6 8

這是解決此問題的最簡單的Java程序。 您可以看到我們已經(jīng)對輸入數(shù)組進(jìn)行了硬編碼，但是您也可以修改程序以通過使用Scanner類從用戶獲取輸入，如本示例所示。

該代碼與解決方案完全相同，我們通過復(fù)制原始數(shù)組的長度來創(chuàng)建另一個(gè)數(shù)組，并使用它標(biāo)記存在的數(shù)字。

由于數(shù)組索引也是整數(shù)，并且它們在輸入值的范圍內(nèi)，因此我們可以利用它們將其用作數(shù)據(jù)和元數(shù)據(jù)。 如果數(shù)組中包含的數(shù)字不在1到N-1之間，那么我們就不能使用數(shù)組。

以下是幻燈片中算法和代碼的摘要，以使您更好地理解：

4.分析

現(xiàn)在，是時(shí)候分析我們的解決方案，以便使用Big O表示法查找CPU和內(nèi)存的復(fù)雜性。 如果看一下代碼，您會(huì)發(fā)現(xiàn)我們正在創(chuàng)建另一個(gè)具有相同大小的數(shù)組，這意味著它的內(nèi)存或空間復(fù)雜度為O（n） 。

這意味著如果數(shù)組太大，即包含整數(shù)范圍內(nèi)的所有數(shù)字，那么我們將有更多的內(nèi)存可能不可用，并且我們的程序可能會(huì)在Java中拋出OutOfMemoryError 。 這甚至更有可能，因?yàn)閿?shù)組需要連續(xù)的內(nèi)存塊。

因此，如果我們可以刪除實(shí)際上不容納任何內(nèi)容的附加數(shù)組，并找到一種方法來存儲(chǔ)丟失的數(shù)字，而該數(shù)字遠(yuǎn)遠(yuǎn)小于我們可以改進(jìn)此解決方案的所有數(shù)字，那么您可以考慮一下。

對于時(shí)間復(fù)雜度 ，您可以看到我們遍歷整個(gè)數(shù)組以標(biāo)記所有存在的數(shù)字，然后再次遍歷具有相同長度的另一個(gè)數(shù)組以查找缺席者。 這意味著該解決方案的時(shí)間復(fù)雜度為O（n）+ O（n）或O（2N），但仍為Big O表示法仍為O（n） 。

如果我們找到在給定數(shù)組中進(jìn)行迭代時(shí)打印缺席者的方法，則可以進(jìn)一步改進(jìn)此解決方案。 再說一遍，你們要想一想。

這就是在給定整數(shù)array中查找缺失數(shù)字的經(jīng)典問題 。 在這一部分中，我們找到了一種解決方案，該解決方案可在未排序的重復(fù)數(shù)組中查找多個(gè)缺失的數(shù)字。 我們解決方案的時(shí)間和空間復(fù)雜度為O（n）。

翻譯自: https://www.javacodegeeks.com/2018/04/how-to-find-k-missing-numbers-in-integer-array-with-duplicates-in-java.html

總結(jié)

以上是生活随笔為你收集整理的如何在Java中使用重复项查找整数数组中的K个缺失数字？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。