[Offer] [3-1] [Find duplicate numbers in arrays]

Topic Description

All numbers in an array of length n are in the range of 0-n-1. Some numbers in the array are repeated, but it is not known how many numbers are repeated, or how many times each number is repeated. Find any duplicate number in the array. For example, if an array {2,3,1,0,2,5,3} with an input length of 7 is input, the corresponding output is a duplicate number 2 or 3.

thinking

  1. Sort and then look for
  2. To solve the problem, a hash table is used to scan the number in the array and add it to the hash table when it is not swept to a number. If the hash table contains the number, the number is a duplicate number. _
  3. Note that the title requires all numbers to be in the range of 0-n-1, which can be extended from the hash table idea to rearrange the array: if the number in the array is stored in the same index position as the number (exchange two digits), if there is an index position duplicate, the number is repeated. _

 

Java code

public class Offer003_01 {
    public static void main(String[] args) {

        int[] arr = { 3, 5, 7, 8, 8, 6, 2, 4, 1 };
        int[] dupArr = new int[2];
        boolean duplicate = Offer003_01.duplicate(arr, dupArr);
        System.out.println(duplicate);
        System.out.println(dupArr[0]);
    }

    public static boolean duplicate(int[] arr, int[] dupArr) {
        return Solution1(arr, dupArr);
    }

    /**
     * 
     * Using the idea of hash table to expand and rearrange arrays
     * @param numbers  Array to pass
     * @return   Repeated figures
     */
    public static boolean Solution1(int[] arr, int[] dupArr) {

        if (arr == null || arr.length <= 0) {// Determine whether an array is empty
            return false;
        }
        for (int i = 0; i < arr.length; i++) {// Determine whether the data in the array is out of range
            if (arr[i] < 0 || arr[i] > arr.length - 1) {
                return false;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != i) {// To determine whether the current element is equal to its subscript i or not, enter the loop
                if (arr[i] == arr[arr[i]]) {// Judging the current element sum
                    dupArr[0] = arr[i];
                    return true;
                }
                // The purpose is to make a[0]=0;a[1]=1 a[2]=2; [2,3,2,1] a [0] = a [0] = a [2] = 2
                int temp = arr[i];
                arr[i] = arr[arr[i]];
                arr[temp] = temp;
            }
        }
        return false;
    }

}

Code Links

Sword Finger Office Code - Java

Tags: PHP Java

Posted on Wed, 09 Oct 2019 23:49:21 -0700 by nyi8083