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

Duplicate numbers in an array

I’ve been reviewing algorithms and data structures (implemented in Python), and I’ve looked at Python’s various “sequences” — lists, tuples, and strings. I’ll write a blog about arrays.

But first let’s take a look at an interview question about arrays from Finger Offer.

Interview question 3: Duplicate numbers in an array

Problem 1: Find duplicate numbers in the array

Given an array of length n in which all the numbers 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.

Sample:

Given nums = [2, 3, 1, 0, 2, 5, 3]

Return 2 or 3

Train of thought

So the first thing we need to understand is that they want to return any number that repeats. There is no limit on other conditions (how much time complexity and space complexity), so there are many ways to solve the problem. Let’s focus on the following solutions:

1. Search after sorting: the simple method is to sort the input array first, the sorted array, directly compare the two adjacent numbers, if there is an adjacent array equal, return the number.
2. Use the hash table: scan each number in the array sequentially from beginning to end, and when it reaches a number, add it to the hash table if it doesn’t already exist. If the number already exists in the hash table table, a duplicate number is found.
3. Time for space: We observe that the way to use hash tables is to increase o(n) O (n)o(n) size hash table at the expense of seeing if we can find o(1) O (1)o(1) algorithm.

Method 1: search after sorting

def find_double_num(nums) : 
    Idea 1: Sort the input array and find duplicate numbers in the sorted array. 
    nums_sorted = sorted(nums) 
    length = len(nums_sorted) 
    for i in range(1, length): 
        if nums_sorted[i] == nums_sorted[i - 1] :print("Repeat number:", nums_sorted[i]) 
            return True 
    return False
Copy the code

Method two: use hash table

def find_double_num2(nums) :
    "" Idea 2: Hash table, scan array from beginning to end for each number, hash table does not have the number added to the hash table. If it exists in the hash table it found a duplicate number.
    hash_map = dict(a)for i, val in enumerate(nums):
        if val in hash_map:
            print("Repeat number:", val)
            return True
        hash_map[val] = i
    return False
Copy the code

Method three: time for space method

def find_double_num3(nums) :
    if nums is None and len(nums) <= 0:
        return False
    for i in range(len(nums)):
        whilei ! = nums[i]:if nums[i] == nums[nums[i]]:
                print("Repeat number:", nums[i])
                return True
            else:
                tmp = nums[i]
                nums[i] = nums[tmp]
                nums[tmp] = tmp
    return False
Copy the code

test

nums_test = [2, 3, 1, 0, 2, 5, 3]
print(find_double_num(nums_test))
print(find_double_num2(nums_test))
print(find_double_num3(nums_test))
Copy the code

Output result:

Repeat number: 2 True Repeat number: 2 True Repeat number: 2 TrueCopy the code

conclusion

In fact, just saw the book of this problem, I feel very familiar. If you think about it, this problem is very similar to LeetCode 01, which is the sum of two numbers. If you’re interested, you can do that, and the code is pretty consistent. You can compare it with the brush.