This article was originally published by Yanglbme on “Nuggets of Gold”.

I will update a series of articles related to sword Offer, one question at a time, “title + idea +AC code”, hoping to help you find friends.

The title

Given a nums array of integers of length N, all the numbers in the array 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.

Note: If some number is not in the range of 0 to N −1, or the array does not contain duplicate numbers, -1 is returned.

The sample

Given nums = [2, 3, 5, 4, 3, 2, 6, 7]. Return 2 or 3.Copy the code

Their thinking

The array is n in length, and all the numbers are in the range 0 to n-1. If the elements are not duplicated, the array should be [0, 1, 2…n-1] (assuming the array is sorted). That is, after ascending sort, the values of the elements in the array should be the same as their corresponding subscripts, that is, the values of the elements with subscripts of 0 should also be 0, and so on.

First, we can iterate through the array and return -1 if there is an element that is not in the range 0 to n-1.

Then, the array is iterated again. If the subscript I is different from the corresponding element nums[I], nums[I]! = I, we should swap the element nums[I] to the correct position nums[I]. Before the swap, check whether nums[I] and nums[nums[I] are the same. If they are the same, the value is returned. Otherwise, the swap is performed. After the swap, we need to judge the element at position I again, so we use the while loop.

Can be compared to the following code implementation, deepen understanding.

100% AC code

class Solution {
    public int duplicateInArray(int[] nums) {
        int n = nums.length;
        
        // If an array element is not in the range [0, n-1], return -1
        for (int num : nums) {
            if (num < 0 || num >= n) {
                return -1; }}for (int i = 0; i < n; ++i) {
            while(nums[i] ! = i) {if (nums[i] == nums[nums[i]]) {
                    Position I is the same as the element at position nums[I]
                    returnnums[i]; } swap(nums, i, nums[i]); }}return -1;
        
    }
    
    private void swap(int[] nums, int i, int j) {
        intt = nums[i]; nums[i] = nums[j]; nums[j] = t; }}Copy the code
_.. _, -- -- -- -- -- -- -- -- -- -- -- -.,' `. ( We want you! ) / __) __ '\' -,----------'((` - ` (-')  ) _.-'/) \ = / (/'| -. \ [- | ` -.) __ `) (` -., -- --'_ ` -.'/,' ( Uu", (_ , `/,-'__,) ` ` -'/ / ` --'
                          |     `--' | ` `-._ / \ ( /\ . \. offer / |` \ ,-\ / \| .) / \ [, '|\    ,': | \, `. ` -- -- "/} `,'    \  |,'/ / "- _ ` - / |" -. "-.'|; / _ / ["-""] : / |"-     ' '           |      /
                                 `      |
Copy the code

If you have any doubts about the solution and code, you can interact with me in the comment section. You can also click “like” and “collect” if you have any gains.

Welcome to follow my wechat public account “Doocs Open Source Community” and push original technical articles as soon as possible.