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

SoapEye 發布于2019-08-19 11:37 / 1377人閱讀

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

題目

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

方法一

創建一個長度為n+1的輔助數組，將原數組逐一復制到輔助數組中。如果原數組被復制的數字為m，則將它復制到輔助數組中下標為m的位置。

時間復雜度：O(n)，空間復雜度：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》

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77569.html

劍指Offer【3】：數組中重復的數字

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

vpants 2019-08-19 11:37 評論0 收藏0
劍指offer之基礎知識數組

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

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

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

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

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

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

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

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