查找重複的號碼


難度級別
經常問 亞馬遜 蘋果 彭博社 谷歌 Microsoft微軟
排列 二元搜尋 兩指針

給定一個 排列 包含(n + 1)個元素且每個元素在1到n之間的數字。 如果只有一個重複元素,請找到重複編號。

範例檔案

輸入:
nums = {1、3、4、2、2}
輸出:
2

輸入:
nums = {3、1、3、4、2}
輸出:
3

查找重複編號的幼稚方法

方法1(蠻力)

從索引0遍歷數組,並檢查每個元素是否在其前面的數組元素中重複。
如果重複,則這是重複元素,否則繼續下一個元素。
時間複雜度= 2)

JAVA代碼

public class FindTheDuplicateElement {
    private static int findDuplicate(int nums[]) {
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            // For every element check if it is repeated in the elements ahead of it
            for (int j = i + 1; j < n; j++) {
                // If repeated, this is the duplicate element
                if (nums[j] == nums[i])
                    return nums[i];
            }
        }
        // No duplicate found
        return -1;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 2, 2};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(findDuplicate(nums));
    }
}

C ++代碼

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    for (int i = 0; i < n; i++) {
        // For every element check if it is repeated in the elements ahead of it
        for (int j = i + 1; j < n; j++) {
            // If repeated, this is the duplicate element
            if (nums[i] == nums[j])
                return nums[i];
        }
    }
    // Duplicate not found
    return -1;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 2, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 3, 4, 2};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
2
3

方法2(排序)

以升序對數組進行排序,重複的元素將彼此相鄰。
遍歷排序後的數組並返回重複元素。
時間複雜度= O(n log(n))

JAVA代碼

import java. util. Arrays;
public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        // Sort the array
        Arrays.sort(nums);
        // Check the adjacent elements
        for (int i = 0; i < n - 1; i++) {
            // If adjacent elements are equal, this is the duplicate element
            if (nums[i] == nums[i + 1])
                return nums[i];
        }
        // No duplicate found
        return -1;
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 2, 2};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(findDuplicate(nums));
    }
}

C ++代碼

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    // Sort the array
    sort(nums, nums + n);
    // Check the adjacent elements
    for (int i = 0; i < n - 1; i++) {
        // If adjacent elements are equal, this is the duplicate element
        if (nums[i] == nums[i + 1])
            return nums[i];
    }
    // Duplicate not found
    return -1;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 2, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 3, 4, 2};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
2
3

查找重複編號的最佳方法

方法1(散列)

創建一個HashSet,並為nums數組的每個元素創建一個HashSet,如果當前元素存在於HashSet中,則該元素為重複元素,否則將該元素插入HashSet中。
時間複雜度= O(N)
空間複雜度= O(N)

用於查找重複編號的JAVA代碼

import java.util.*;
public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        // Create a HashSet
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            // If the HashSet contains the element, then this is the duplicate
            if (set.contains(nums[i]))
                return nums[i];
            // Else add the element to the set
            set.add(nums[i]);
        }
        // No duplicate found
        return -1;
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 1, 2, 5};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 4, 2, 5, 5};
        System.out.println(findDuplicate(nums));
    }
}

查找重複編號的C ++代碼

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    // Create a HashSet
    unordered_set<int> set;
    for (int i = 0; i < n; i++) {
        // If the HashSet contains the element, then this is the duplicate
        if (set.find(nums[i]) != set.end())
            return nums[i];
        // Else add the element to the set
        set.insert(nums[i]);
    }
    // Duplicate not found
    return -1;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 1, 2, 5};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 5, 4, 2, 5};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
1
5

方法2(XOR)

根據XOR屬性(X ^ X)= 0,此屬性可用於解決上述問題。

  1. 初始化一個整數X作為元素從1到n的XOR,其中nums數組的大小為(n + 1)。
  2. 將另一個整數Y初始化為0。
  3. 遍歷數組並將Y更新為(Y ^ nums [i]),即Y存儲nums數組的所有元素的XOR。
  4. 重複元素是(X ^ Y)。

時間複雜度= 上), 有兩次遍歷,一次遍歷X,一次遍歷Y
空間複雜度= O(1)

用於查找重複編號的JAVA代碼

public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        // Initialise X as XOR of elements from 1 to n
        // Size of nums is (n + 1), here represented as n
        int X = 0;
        for (int i = 1; i <= n - 1; i++)
            X = (X ^ i);

        // Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
        int Y = 0;
        for (int i = 0; i < n; i++) {
            Y = Y ^ nums[i];
        }
        
        // Duplicate element is (X ^ Y)
        return (X ^ Y);
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 2, 4};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(findDuplicate(nums));
    }
}

查找重複編號的C ++代碼

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    // Initialise X as XOR of elements from 1 to n
    // Size of nums is (n + 1), here represented as n
    int X = 0;
    for (int i = 1; i <= n - 1; i++)
        X = X ^ i;
    
    // Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
    int Y = 0;
    for (int i = 0; i < n; i++)
        Y = Y ^ nums[i];
    
    // Duplicate element is (X ^ Y)
    return (X ^ Y);
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 2, 4};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 3, 4, 2};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
4
3

方法3(週期檢測)

上述問題可以通過鍊錶中的循環查找算法來解決,該算法使用慢速和快速兩個指針,在每次迭代中慢速指針移動一步,快速指針移動兩步。

考慮這個例子,
nums [] = {1、3、4、2、2}

查找重複的號碼

  1. 初始化兩個指針,慢速和快速初始化為nums [0]。
  2. 當slow和fast不相等時,請執行slow = nums [slow]和fast = nums [nums [fast]]。
  3. 在第2步之後,將lower分配為nums [0],並分別將慢速指針和快速指針移動一步,即,
    slow = nums [slow]
    fast = nums [快速]
    而慢和快並不相等。
  4. 步驟3之後,慢速和快速都指向重複元素。

時間複雜度= O(N)
空間複雜度= O(1)

用於查找重複編號的JAVA代碼

public class FindTheDuplicateElement {
    private static int findDuplicate(int[] nums) {
        int n = nums.length;
        //Initialize two pointers slow and fast as nums[0].
        int slow = nums[0], fast = nums[0];
        // Do slow = nums[slow] and fast = nums[nums[fast]]
        // while slow and fast are not equal.
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // assign slow as nums[0]
        slow = nums[0];
        // Move slow and fast by one step each while slow and fast are not equal
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        // Both slow and fast points to the duplicate element
        return fast;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 3, 4, 4, 2};
        System.out.println(findDuplicate(nums));

        // Example 2
        nums = new int[]{3, 1, 5, 4, 2, 5};
        System.out.println(findDuplicate(nums));
    }
}

查找重複編號的C ++代碼

#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
    //Initialize two pointers slow and fast as nums[0].
    int slow = nums[0], fast = nums[0];
    // Do slow = nums[slow] and fast = nums[nums[fast]]
    // while slow and fast are not equal.
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // assign slow as nums[0]    
    slow = nums[0];
    // Move slow and fast by one step each while slow and fast are not equal
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    // Both slow and fast points to the duplicate element
    return fast;
}

int main() {
    // Example 1
    int nums[] = {1, 3, 4, 4, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    cout<<findDuplicate(nums, n)<<endl;
    
    // Example 2
    int nums2[] = {3, 1, 5, 4, 2, 5};
    n = sizeof(nums2) / sizeof(nums2[0]);
    cout<<findDuplicate(nums2, n);
    
    return 0;
}
4
5

參照e1   參考2