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

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

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

題目

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

方法一

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

時(shí)間復(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》

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77569.html

相關(guān)文章

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

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

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

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

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

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

XUI 2021-11-12 10:36 評(píng)論0 收藏0
劍指offer--JavaScript版

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

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

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

xavier 2021-10-12 10:12 評(píng)論0 收藏0