@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency

1, dry

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 Limit: 2 <= n <= 100000 Pass count 330,298 Submit Count 488,116Copy the code

2, hash table

From the data structures you’ve learned so far, it’s easy to think of a hash table that keeps track of the number of digits in an array. When the number of times is not 1, there must be more than one number, so the repeated number is directly returned.

Algorithm flow:

  1. Initialize: create a hash table map, call it hash, the first position is the number, the second position is the number;
  2. Iterate over each nums in numS [I] :
    1. Add nums[I] to hash;
    2. If nums[I] is not 1, it is repeated and nums[I] is returned.
  3. Returns -1, no duplicate number found, returns -1.
// Interview question 03. Duplicate numbers in array
/ / map storage
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        map<int.int> hash;
        for(int i = 0; i < nums.size(a); ++ i) { hash[nums[i]] ++ ;if(hash[nums[i]] ! =1) return nums[i];
        }
        return - 1; }};Copy the code

// Equivalent code
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
    	//unordered_map<int, int> hash;
        map<int.int> hash;
        //for(int i = 0; i < nums.size(); ++ i)
        for(int num : nums)
        {
            hash[num] ++ ;
            if(hash[num] ! =1) return num;
        }
        return - 1; }};Copy the code

3, in situ replacement

Since the length of the array is N and the number is 0-n-1, the index can be the same as the number of the index in the array, but the same index must be repeated for multiple numbers.

Algorithm flow:

  1. Iterate over each nums in numS [I] :
    1. Nums [I] == nums[nums[I]], indicating that the number is the same as the number indexed by the number.
    2. When the nums [I]! = nums[nums[I]], can be exchanged to conform to 1.1;
  2. If nums[I] == I, return nums[I];
  3. Returns -1, no duplicate number found, returns -1
// Interview question 03. Duplicate numbers in array
// Standard practice
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0; i < nums.size(a); ++ i) {while(nums[i] ! = nums[nums[i]])swap(nums[i], nums[nums[i]]);
            if(nums[i] ! = i)return nums[i];
        }
        return - 1; }};Copy the code

4. Complexity

/* Although there is a double loop in the code, each number needs to be swapped at most twice to find its place, so the total time is O (n). In addition, all operations are performed on the input array and no additional memory allocation is required, so the space complexity is O (1). * /
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…