How to implement query for repeated numbers in an array in Java

The content of this article is about how to query repeated numbers in an array in Java. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Question 1: Find duplicate numbers in the array.

All numbers in an array of length N are within the range of 0-n-1. Some numbers in the array are repeated, but I don’t know how many numbers are repeated. I don’t know how many times the number is repeated. Please find any repeated number in the array.

Solution 1: Sort this array. It is very easy to find duplicate numbers from the sorted array. Just scan the sorted array from beginning to end. Sorting an array of length N requires O(nLogn) time.

Solution 2: Use a hash table to solve the problem. Scan each number in the array from beginning to end. Each time a number is scanned, determine whether the number is in the hash table. This The time of the algorithm is O(N), but its time efficiency comes at the expense of a hash table of size O(N).

Solution 3: We rearrange the array and scan each number in the array from beginning to end. When the number with subscript i is scanned, compare the value of this number (m) Is it equal to i? If it is equal, the value of m is paid to i. If it is not equal, compare it with the value corresponding to the m subscript until all repeated values ​​are found.

The above is the detailed content of How to implement query for repeated numbers in an array in Java. For more information, please follow other related articles on the PHP Chinese website!