劍指Offer【3(2)】：不修改數(shù)組找出重復(fù)的數(shù)字

SoapEye 發(fā)布于2019-08-19 11:37 / 1447人閱讀

摘要：題目在一個長度為的數(shù)組里面的所有數(shù)字都在的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長度為的數(shù)組，那么對應(yīng)的輸出是重復(fù)的數(shù)字或者。

題目

在一個長度為n+1的數(shù)組里面的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長度為9的數(shù)組{2,3,5,4,3,2,6,7}，那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3。

方法一

創(chuàng)建一個長度為n+1的輔助數(shù)組，將原數(shù)組逐一復(fù)制到輔助數(shù)組中。如果原數(shù)組被復(fù)制的數(shù)字為m，則將它復(fù)制到輔助數(shù)組中下標(biāo)為m的位置。

時間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)

public static boolean test(int[] array){
        if(array == null || array.length<=0){
            return false;
        }
        
        for(int i=0;i=array.length || array[i]<=0){
                return false;
            }
        }
        int[] arr = new int[array.length];
        for(int i=0;i
參考：《劍指Offer》

云服務(wù)器 GPU云服務(wù)器不重復(fù)隨機數(shù)組找出一個二維數(shù)組中的鞍點 js查找數(shù)組中重復(fù)的 WebRTC源碼offer不觸發(fā)事件

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/77569.html

相關(guān)文章

劍指Offer【3】：數(shù)組中重復(fù)的數(shù)字

摘要：題目描述在一個長度為的數(shù)組里的所有數(shù)字都在到的范圍內(nèi)。請找出數(shù)組中任意一個重復(fù)的數(shù)字。例如，如果輸入長度為的數(shù)組，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字。判斷數(shù)組是否為空參考劍指題目描述在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。例如，如果輸入長度為7的數(shù)組{2,...

vpants 2019-08-19 11:37 評論0 收藏0
劍指offer之基礎(chǔ)知識數(shù)組

摘要：附上和實現(xiàn)二維數(shù)組中的查找題目描述在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。為了實習(xí)的準(zhǔn)備，開始刷題來鞏固基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)，大神輕噴。 1.數(shù)組中重復(fù)的數(shù)字題目描述：在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有...

zhou_you 2019-08-22 13:49 評論0 收藏0
【劍指 Offer II】 082. 含有重復(fù)元素集合的組合

摘要：題目給定一個可能有重復(fù)數(shù)字的整數(shù)數(shù)組和一個目標(biāo)數(shù)，找出中所有可以使數(shù)字和為的組合。中的每個數(shù)字在每個組合中只能使用一次，解集不能包含重復(fù)的組合。示例輸入輸出示例輸入輸出提示注意本題與主站題相同答案回溯法排序后去重 ...

XUI 2021-11-12 10:36 評論0 收藏0
劍指offer--JavaScript版

摘要：劍指在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。其中負數(shù)用補碼表示。本文為8月?？途W(wǎng)《劍指 offer》刷題做得，現(xiàn)整理出來作為參考。雖然是算法題，但本文用 JavaScript 編寫，看了《劍指 offer》以后發(fā)現(xiàn)很多問題處理的過程并不是最好的，所以本文僅供參考。以前全部代碼 A...

MarvinZhang 2019-08-23 11:52 評論0 收藏0
【劍指offer系列刷題】第一篇——尋找單身狗

摘要：劍指系列刷題第一篇題目來源數(shù)組中數(shù)字出現(xiàn)的次數(shù)大家可以去測試一下自己的代碼博主碼云鏈接文章目錄前言題目描述解題思路解題代碼前言這是劍指系列刷題第一篇文章，大家可以互相學(xué)習(xí)一下。其中的兩個單身狗是和。 ...

xavier 2021-10-12 10:12 評論0 收藏0