Topic describes

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 3Copy the code

Limitations:

2 <= n <= 100000

Answer key

The first thing that comes to mind when you get this problem is to use a map to process through the entire array. When a number’s value in the map is true, it means that the number has appeared before.

However, if the interviewer asks for space complexity O(1) during the interview, you cannot use an additional array of markers or map. For such array elements in the range [0, n-1], we can replace the value of I with the index of I by in place substitution. If the subscript I is preceded by a number with the corresponding value of I, the number I is repeated.

Use the example given in the question to simulate this process:

0 1 2 3 4 5 6 subscript 2, 3, 1 2 3 initial value 1 2 3 0 0 2 3 0 subscript 2 and 5 subscript 2 replacement 3 1 2 0 0 2 5 3 subscripts 1 and the subscript 1 3 replacement 5 subscript 3 0 0 1 2 3 2 3 and the subscript 3 0 substitution 0 1, 2, 3, 2, 5, 3 the value of subscript 2 is already 2, and the 2 on subscript 4 cannot be replaced with it, so 2 is a repeated numberCopy the code

The source code

package main

import "fmt"

func main(a) {
	var nums = []int{2.3.1.0.2.5.3}
	fmt.Println(findRepeatNumber(nums))
	fmt.Println(findRepeatNumber2(nums))
}

func findRepeatNumber(nums []int) int {
	var m = make(map[int]bool.len(nums))
	for _, num := range nums {
		if m[num] {
			return num
		}
		m[num] = true
	}
	return 0
}

// In place substitution method
func findRepeatNumber2(nums []int) int {
	for i, num := range nums {
		fornums[i] ! = i {if nums[i] == num {
				return nums[i]
			}
			nums[i], num = num, nums[i]
		}
	}
	return 0
}
Copy the code
#include <iostream>
#include <vector>

using namespace std; 

bool duplicate(int numbers[], int length, int *duplication) {
    vector<bool> b = {0};
    for (int i = 0; i < length; i++) {
        if (b[numbers[i]]) {
            *duplication = numbers[i];
            return true;
        }
        b[numbers[i]] = true;
    }
    return false;
}

int main(a) {
    ios::sync_with_stdio(false);
    int n, res;
    int a[1001];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << duplicate(a, n, &res) << endl;
    cout << res;
    return 0;
}
Copy the code