一、找出數(shù)組中的重復(fù)數(shù)字

描述
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。 例如，如果輸入長度為7的數(shù)組[2,3,1,0,2,5,3]，那么對應(yīng)的輸出是2或者3。存在不合法的輸入的話輸出-1

數(shù)據(jù)范圍：
進階：時間復(fù)雜度，空間復(fù)雜度
輸入：[2,3,1,0,2,5,3]
返回值：2
說明：
2或3都是對的

采用重排數(shù)組的辦法，時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)；
首先，我們可以遍歷數(shù)組，若存在元素不在 0~n-1 的范圍內(nèi)，直接返回 -1。
接著，再次遍歷數(shù)組，若下標 i 與對應(yīng)元素 nums[i] 不同，即 nums[i] != i，我們應(yīng)該把 nums[i] 這個元素交換到正確的位置 nums[i]上。交換前，先判斷 nums[i] 與 nums[nums[i]] 這兩個元素是否相同，相同說明存在重復(fù)元素，直接返回，否則進行 swap 交換。交換過后，我們需要再次判斷 i 位置上的元素，因此，我們使用 while 循環(huán)。
從頭到尾依次掃描數(shù)組中每一個數(shù)字。當(dāng)掃描到第i個元素時，比較該位置數(shù)值m是否等于i。若是，接著掃描下一個數(shù)字；否則，將其與第m個數(shù)字進行比較。若相等，則返回該重復(fù)數(shù)字；否則，交換兩個數(shù)字，繼續(xù)重復(fù)前面的過程。

public class Solution {/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可 * @param numbers int整型一維數(shù)組 * @return int整型*/public int duplicate (int[] numbers) {// write code hereint n = numbers.length;int i =0;while(i<n){if(numbers[i]<0 || numbers[i]>=n)return -1;if(numbers[i]==i){i++;continue;}else{if(numbers[i]==numbers[numbers[i]]){return numbers[i];}int temp=numbers[i];numbers[i] = numbers[temp];numbers[temp] = temp;}}return -1;} }

二、不修改數(shù)組找出重復(fù)的數(shù)字

題目描述

在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，其中?。所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長度為8的數(shù)組{2,3,5,4,3,2,6,7}，那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3。
測試用例
長度為n的數(shù)組中包含一個或多個重復(fù)數(shù)字
數(shù)組中不包含重復(fù)的數(shù)字
無效輸入測試用例(空指針)
本題的測試用例如下：

int main(){
// 測試用例：
Solution sol;

// 長度為n的數(shù)組中包含一個或者多個重復(fù)數(shù) vector<int> nums1{1,2,3,4,5,5,6,6,7}; // expected output: 5/6 cout << sol.duplicateInArray(nums1) << endl;

?
vector nums2{3,1,2,3}; // expected output: 3
cout << sol.duplicateInArray(nums2) << endl;
?
vector nums3{1,1}; // expected output: 1
cout << sol.duplicateInArray(nums3) << endl;
}

哈希表：跟上一題一樣，本題也可以創(chuàng)建一個哈希表，如果原數(shù)組的每個數(shù)字第一次出現(xiàn)，就把他放到哈希表中去，即原數(shù)組大小為m的數(shù)字應(yīng)該放到哈希表下標為m的位置上。空間復(fù)雜度是 。
1、二分法：那么有沒有不用空間復(fù)雜度 的算法。假設(shè)沒有重復(fù)數(shù)，那么 1~n 之間，每個數(shù)都只能出現(xiàn)一次。而題目中，這個數(shù)組至少有一個數(shù)字重復(fù)，即出現(xiàn)的次數(shù)大于1。
2、利用二分的思想：把 1~n 的數(shù)字從中間數(shù)字m開始分為兩部分，前一半為 1~ m，后面一半為 m+1 ~n，如果 1~m 中的數(shù)字在數(shù)組中出現(xiàn)的次數(shù)大于m，那么這一半必定有重復(fù)的數(shù)字；否則，那么另一部分必定含有重復(fù)數(shù)字。接著我們，繼續(xù)對含有重復(fù)數(shù)字的區(qū)間一分為二，直到找到重復(fù)的數(shù)字。

總結(jié)

以上是生活随笔為你收集整理的剑指offer-week1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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