Pay attention to the public number “qinhuai grocery store” can receive sword finger Offer V1 version of PDF solution, V2 version increased the topic, but also in the update, and for each topic increased C++ solution, please look forward to.

3. Duplicate numbers in the array

Topic describes

All the numbers in an array of length N are in the range 0 to n minus 1. Some numbers in the array are duplicated, but it is not known how many are duplicated. I don’t know how many times I repeat each number. Find the first duplicate number in the array. For example, if you input an array of length 7 [2,3,1,0,2,5,3], the corresponding output is the first repeated number 2. Returns -1 for no duplicate numbers.

Example 1

The input

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

The return value

2

Ideas & Solutions

The first thing you might want to do with a set is add an element to it if it’s not in the set, and return it if it’s in the set. If there is no repeat, then -1 is returned.

The Java code is as follows:

import java.util.*;
public class Solution {
    public int duplicate(int[] numbers) {
        if(numbers ! =null) {
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < numbers.length; i++) {
                if (set.contains(numbers[i])) {
                    return numbers[i];
                } else{ set.add(numbers[i]); }}}return -1; }}Copy the code

The C++ code is as follows:

#include <iostream>
#include <vector>
#include<set>

using namespace std;

class Solution {
public:
    int duplicate(vector<int> &numbers) {
        if(! numbers.empty()) {
            set<int> mySet;
            for (int i = 0; i < numbers.size(a); i++) {if (mySet.count(numbers[i]) <= 0) {
                    return numbers[i];
                } else {
                    mySet.insert(numbers[i]); }}}return - 1; }};Copy the code

The time complexity of the above code is O(n), because the worst-case scenario is to iterate through all the elements; The space complexity is also O(n), and the maximum set size is N.

Because all numbers are in the range 0 to n-1, we can count all numbers with an array of size N. If the number is more than 1, it must be a duplicate number. If there are no duplicate numbers, it returns -1.

Java code implementation:

public class Solution {
    public int duplicate(int[] numbers) {
        if(numbers ! =null) {
            int[] nums = new int[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                if (nums[numbers[i]] == 1) {
                    return numbers[i];
                } else {
                    nums[numbers[i]] = 1; }}}return -1; }}Copy the code

C++ code implementation:

#include <iostream>
#include <vector>
#include<set>

using namespace std;

class Solution {
public:
    int duplicate(vector<int> &numbers) {
        if(! numbers.empty()) {
            int nums[numbers.size()];
            for (int i = 0; i < numbers.size(a); i++) {if (nums[numbers[i]] == 1) {
                    return numbers[i];
                } else {
                    nums[numbers[i]] = 1; }}}return - 1; }};Copy the code

Again, this approach is O(n) in both time and space, without much optimization.

So is there any space complexity zeroO(1)What about the practice?

There is, of course, no extra space, so you just have to manipulate the original array. If there are no duplicates, then the number I should correspond to the array subscript I. You don’t have multiple I’s.

Based on this principle, when we iterate over the array, we adjust the element I to the position of the subscript I. If there is already an element at the position of the subscript I, then there is a conflict and the element must be duplicated. Otherwise, we continue to adjust the following elements. If no duplicate numbers are found, -1 is returned.

Java code implementation is as follows:

public class Solution {
    public int duplicate(int[] numbers) {
       int i = 0;
        while(i < numbers.length) {
            if(numbers[i] == i) {
                i++;
                continue;
            }
            if(numbers[numbers[i]] == numbers[i]) return numbers[i];
            int tmp = numbers[i];
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
        return -1; }}Copy the code

C++ code implementation is as follows:

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int duplicate(vector<int> &numbers) {
        int i = 0;
        while (i < numbers.size()) {
            if (numbers[i] == i) {
                i++;
                continue;
            }
            if (numbers[numbers[i]] == numbers[i]) {
                return numbers[i];
            }
            int tmp = numbers[i];
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
        return - 1; }};Copy the code

However, the above method is not suitable for solving multiple repeated digits, because when switching, it is easy to switch the following digits to the front, resulting in not the first repeated digits (can be used to solve any repeated digits), but the second, third digits… Or some other repeated number. For example: [6,3,2,0,2,5,0] The correct solution would be 2, but by switching 6 the first time with the last 0, the result would be 0.

[Author profile] : Qin Huai, public number [Qin Huai Grocery store] author, the road of technology is not at that time, mountain high water long, even slow, chi and not stop. Personal Writing Direction: Java source code analysis, JDBC, Mybatis, Spring, Redis, distributed, sword Offer, LeetCode, etc., carefully write each article, do not like the title party, do not like the flowery, mostly write a series of articles, can not guarantee that I write are completely correct, But I guarantee that what I write is done through practice or research. We hope to correct any omissions or mistakes.

Offer all questions in PDF

What did I write about 2020?

Open Source Programming Notes