Reference to duplicate number in Offer 03 array

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1, the title

Find duplicate numbers in the array.

All numbers in an array of length N, nums, are in the range 0 to n-1. Some numbers in the array are repeated, but we don’t know how many are repeated, or how many times each number is repeated. Please find any duplicate number in the array.

Example 1:

Input: [2, 3, 1, 0, 2, 5, 3]

Output: 2 or 3

Example 2:

Input: [2, 3, 1, 3]

Output: 3

Tip:

  • 2 <= n <= 100000

2, train of thought

Method one:

  1. Sort the array

  2. After sorting, determine whether adjacent elements are equal

    • If equal, the element is repeated and the value of the element is returned
    • If not, continue to move back

Method 2: hash table/Set

Since we only need to find any duplicate number in the array, we walk through the array and determine the hash table if we encounter a duplicate number. To determine if a number is encountered twice, the set is used to store numbers that have already been encountered. If a number encountered is already in the set, the current number is a repeated number.

  • Initialize collection

  • Iterate over each element in the array

    • Determines whether the element exists in the collection

      • If it exists, the element is already in the collection, so it is a repeating element and returns its value directly
      • If not, the element is not in the collection and needs to be added to the collection

Method 3:

If there are no duplicate digits, the subscript of the number I is also I after normal sorting, so in this vein, scan the array again and encounter a number with subscript I. If the value of the current position is not I, (let’s say x) swap the current position with the number with the subscript x. If a duplicate number occurs during the exchange, it is not executed.

Less nonsense ~~~~~ on the code!

3, code,

Commit AC for the first time

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == nums[i + 1]) {returnnums[i]; }}return -1; }}Copy the code

Commit the SECOND TIME

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for(int num : nums){
            if(numSet.contains(num)) return num;
​
            numSet.add(num);
        }
        return -1; }}Copy the code

Time complexity O(N) : Traversal number group uses O(N), HashSet addition and lookup elements are O(1). Space complexity O(N) : The HashSet takes up O(N) of additional space.

Commit AC for the third time

class Solution {
    public int findRepeatNumber(int[] nums) {
        if(nums.length == 0) return -1;
        for(int i = 0; i < nums.length ; i++){
            // Check whether the current position matches the value of the position
            // For example nums[1] == 1
            while(nums[i] ! = i){//nums[1] ! = 1 Determines whether the value at this position is equal to the value at the index
                // Returns the current value if it is equal
                if(nums[i] == nums[nums[i]]) return nums[i];
​
                // Otherwise swap the position to the index of the value
                inttemp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; }}return -1; }}Copy the code

Time complexity O(N) : The traversal number group uses O(N), and the judgment and exchange operation of each traversal uses O(1). Space complexity O(1) : Extra space with constant complexity.

4, summarize

The topic examines a unique understanding of arrays, the state of sorted arrays, and an understanding of hash tables.

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

Duplicate number in array Offer 03