「每日一題」與面試官手撕程式碼：如何科學高效的尋找重複元素？

「每日一題」與面試官手撕程式碼：如何科學高效的尋找重複元素？

關注公眾號「松寶寫程式碼」，精選好文，每日一題

加入我們一起學習，day day up

經過三天時間，已經有小夥伴（xpf666）給我們貢獻文章了，超級開心和激動，因為我們不是一個人在戰鬥，
不是一個人在努力提高自己，加入我們，

如何加入我們？

第一步：文章下面留言，留言內容：想寫什麼文章。

第二步：我們就會找到你

作者：xpf666

來源：原創

一、前言

2020.12.23 日剛立的 flag，每日一題，題目類型不限制，可以是：演算法題，面試題，闡述題等等。

本文是「每日一題」第 4 題，由 xpf666 帶來的文章：如何科學高效的尋找重複元素？

每日一题

往期「每日一題」：

//mp.weixin.qq.com/s/QuuPd2KCp50snN7F2o3oYg

//mp.weixin.qq.com/s/omeVJdtabo5MeN3DItDfWg

//mp.weixin.qq.com/s/O8j9gM5tD5rjLz1kdda3LA

二、尋找重複元素

1. 找出任意一個重複數字

給定一個長度為 n 的數組 nums，判斷是否有重複值。

示例：輸入[1,2,3,2,1,4,5] 輸出 1 或 2

思路：根據經驗，基本上所有判斷重複的需求，都可以通過 Set 或者 Map 解決，Set 解決方式就是判斷 add 方法的返回是 true 還是 false，false 就證明之前已存在，也就是數據重複。Map 是通過 containsKey，true 就說明之前存在 key。

題解：

public int getResult(int[] nums) {
    Set<Integer> set = new HashSet<Integer>();
    int result = -1;
    for (int num : nums) {
        if (!set.add(num)) {
            result = num;
            break;
        }
    }
    return result;
}

如果上面程式碼格式出現問題，可以查看下面程式碼圖片

找出任意一个重复数字

遍歷 n 次並且 Set 內容最多是 n 個字元，複雜度都是 O(n)

2. 找出任意一個重複數字

給定一個長度為 n 的數組 nums，判斷是否有重複值,並且兩個重複值距離不超過 k。

示例：輸入[1,2,3,2,1,4,5] ，k = 2 輸出 true(兩個 2)

思路：同問題一，只要多判斷一次 Set 長度即可。

題解：

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<Integer>();
    boolean result = false;
    for (int i = 0; i < nums.length; i++) {
        if (!set.add(nums[i])) {
            result = true;
            break;
        }

        if (set.size() > k) { // 超過長度就刪除最遠的一個數
            set.remove(nums[i-k]);
        }
    }
    return result;
}

如果上面程式碼格式出現問題，可以查看下面程式碼圖片

找出任意一个重复数字

遍歷 n 次並且 k 最多 n 個字元，複雜度都是 O(n)

3. 尋找重複數

給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和
n），只有一個重複的整數，找出這個重複的數字。

示例：輸入[1,3,4,2,2] 輸出 2

思路：可通過問題 1 方式解決。還可以通過快慢指針法解決：將數組看成一個鏈表，下標為當前指針（node），值指向下一指針(nextNode)，數組出現重複的數字意味著有兩個指針的 nextNode 相同。然後通過快慢指針法解決。

題解：

public int getResult(int[] nums) {
    int result = 0;
    int slow = 0, fast = 0;
    do  {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    do {
        slow = nums[slow];
        result = nums[result];
    } while (result != slow);
    return result;
}

如果上面程式碼格式出現問題，可以查看下面程式碼圖片

找出任意一个重复数字

遍歷 2n 次時間複雜的是 O(n)，只用了常量個字元，空間複雜度是 O(1)

4. 只出現一次的數

給定一個數組
nums，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

示例：輸入[1,1,4,2,2] 輸出 4

思路：可通過問題 1 方式解決。還可以通過位運算解決，兩個相同數異或後為 0，數組所有元素執行一次異或操作，剩下就是出現一次的數。

題解：

public int getResult(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result = result ^ num;
    }
    return result;
}

如果上面程式碼格式出現問題，可以查看下面程式碼圖片

找出任意一个重复数字

遍歷 n 次時間複雜的是 O(n)，只用了常量個字元，空間複雜度是 O(1)

5. 只出現一次的數

給定一個數組
nums，除了兩個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

示例：輸入[1,1,3,4,2,2] 輸出[3,4]

思路：可通過問題 1 方式解決。還可以通過位運算解決，和題 4 區別是存在 2 個只出現一次的數，所以要想辦法把這兩個數區分出來。先將數組所有元素異或，得出的值是兩個只出現一次元素 a,b 的異或值 numsXOR（如 10010）。numsXOR 二進位中 1 的位就是 a 和 b 差異位（因為不同的值異或才是 1），現在只需要找 lowbit(最右一位差異值，10)，然後通過 lowbit 和 a
, b
進行與運算（&），得出的值就一定不同，這樣可以分出 a 和 b，最後按照異或運算就能得出結果（其他重複的不用管，不管分到哪一組，重複的數異或都是 0）

題解：

public int[] singleNumber(int[] nums) {
    int[] results = new int[]{0,0};
    int numsXOR = 0; // 兩個數異或值
    for (int num : nums) {
        numsXOR = numsXOR ^ num;
    }

    int lowBit = numsXOR & (-numsXOR); // lowbit值，用於區分a和b

    for (int num : nums) {
        if ((lowBit & num) == 0) {
            results[0] = results[0] ^ num;
        } else {
            results[1] = results[1] ^ num;
        }
    }

    return results;
}

如果上面程式碼格式出現問題，可以查看下面程式碼圖片

找出任意一个重复数字

遍歷 2n 次時間複雜的是 O(n)，只用了常量個字元，空間複雜度是 O(1)

各種福利

關注「松寶寫程式碼」，後台回復

1、位元組內推福利

回復「校招」獲取內推碼

回復「社招」獲取內推

回復「實習生」獲取內推

後續會有更多福利

2、學習資料福利

回復「演算法」獲取演算法學習資料

3、每日一題

//mp.weixin.qq.com/s/QuuPd2KCp50snN7F2o3oYg

//mp.weixin.qq.com/s/omeVJdtabo5MeN3DItDfWg

//mp.weixin.qq.com/s/O8j9gM5tD5rjLz1kdda3LA

謝謝支援

1、喜歡的話可以「分享，點贊，評論」三連哦。

2、作者昵稱：saucxs，songEagle，松寶寫程式碼。字節跳動的一枚前端工程師，一個正在努力成長的作者，星辰大海，未來可期，內推字節跳動各個部門各個崗位。

3、長按下面圖片，關注「松寶寫程式碼」，是獲取開發知識體系構建，精選文章，項目實戰，實驗室，每日一道面試題，進階學習，思考職業發展，涉及到JavaScript，Node，Vue，React，瀏覽器，http等領域，希望可以幫助到你，我們一起成長～

松宝写代码

Tags:

VirMach 便宜 VPS