Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "how to find repeated numbers in a given array". Many people will encounter such a dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Original topic

Given an array of n + 1 integers whose numbers are between 1 and n (including 1 and n), it is known that there is at least one duplicate integer. Suppose there is only one repeating integer, find out the repeated number.

Example 1:

Input: [1, 3, 4, 2, 2]

Output: 2

Example 2:

Input: [3, 1, 3, 4, 2]

Output: 3

Description:

The original array cannot be changed (assuming the array is read-only).

Only extra O (1) space can be used.

The time complexity is less than O (N2).

There is only one repeated number in the array, but it may be repeated more than once.

Common ideas for solving problems

In view of the first two items in the description, they actually correspond to two ways of solving the problem:

First sort in place, and then traverse to find.

Use the collection to record the numbers that have already appeared.

Of course, now that it has been banned in the instructions, it is time to think of something else.

I also thought of the idea of using bitMap, which is equivalent to using the binary of a number to indicate whether the number has ever appeared or not. However, considering that the maximum value of int in java is (2 ^ 31-1) and the maximum value of long is only (2 ^ 63-1), it is required that n cannot be greater than 100. Therefore, this kind of thinking is not advisable for the time being.

Abstracted as circular linked list II

If the subscript and values of the array are abstracted into a linked list, the presence of duplicate numbers means that there are rings in the linked list, then this problem is exactly the same as the previous force buckle 142 color-ring linked list II.

For example, suppose the array is [1, 5, 7, 3, 2, 4, 6, 7], then the linked list is: 0-> 1-> 5-> 7-> 3-> 2-> 4-> 6-> 7. An infinite loop.

Then we can use the speed pointer:

The fast pointer takes two steps at a time, and the slow pointer takes one step at a time until they meet.

The fast pointer starts from the starting point again, but at this time both pointers take one step at a time.

When they meet again, the meeting point is a repeated integer.

Next, let's look at the code:

Class Solution {

Public int findDuplicate (int [] nums) {

/ / refer to the circular linked list II, using fast and slow pointers

/ / the fast pointer takes two steps at a time, the slow pointer takes one step at a time, when they meet

/ / the fast pointer starts from the starting point again, but at this time both pointers take one step at a time

/ / when they meet again, the meeting point is a repeated integer.

Int slow = nums [0]

Int fast = nums [nums [0]]

While (slow! = fast) {

Slow = nums [slow]

Fast = nums [fast]

}

Fast = 0

While (slow! = fast) {

Slow = nums [slow]

Fast = nums [fast]

}

Return fast

}

}

Submit OK, time complexity: O (n), space complexity: O (1).

This is the end of the content of "how java looks for duplicate numbers in a given array". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.