Shulou(Shulou.com)05/31 Report--

Most people do not understand the knowledge points of this article "Python does not modify the array how to find duplicate numbers", so the editor summarizes the following contents, detailed contents, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "Python does not modify the array how to find duplicate numbers" article.

Duplicate numbers in an array

In the previous blog question 3: repeated numbers in the array of interview questions for Offer, you can find that the key to this kind of questions is to look up the elements that meet the conditions while traversing the array.

Then we introduced the nature of the structure of arrays in our blog post on learning arrays in the most complex way (Python implements dynamic arrays), and implemented a dynamic array ourselves.

Today we introduce another face-to-face test on the array from Jian Zhi Offer-- finding duplicate numbers without modifying the array.

Do not modify the array to find duplicate numbers

Topic 2: do not modify the array to find duplicate numbers

Given that all the numbers in an array of length 1 are in the range of 0 ∼ n, at least one number in the array is duplicated.

Please find any duplicate number in the array, but you cannot modify the entered array.

Example:

An array of length 8 nums = [2, 3, 5, 4, 3, 2, 6, 7]

Then output the duplicate number 2 or 3

Train of thought

First of all, we have to note that the requirement of the topic is: do not modify the array, and then return any duplicate number. So there are fewer ideas to solve the problem:

1. Hash table: like the previous question, this question can also create a hash table. If each number of the original array appears for the first time, put it in the hash table, that is, the number of the original array size m should be placed in the position of the hash table subscript m. The space complexity is $O (n) $.

two。 Dichotomy: then there is no algorithm without the space complexity of $O (n) $. Assuming that there are no repeated numbers, then each number can only appear once between 1n. In the title, the array has at least one number repeated, that is, the number of occurrences is greater than 1.

Using the idea of dichotomy: divide the number of 1cm into two parts starting with the middle number m, the first half is 1cm and the second half is m ~ n. If the number of numbers in 1cm is greater than m in the array, then there must be repeated numbers in this half.

Otherwise, the other part must contain duplicate numbers. Then we continue to split the interval containing duplicate numbers in two until we find the duplicate number.

Idea 1: hash table def find_duplicated_num (nums): "hash_map" hash_map = dict () for I, val in enumerate (nums): if val in hash_map: return val hash_ map [Val] = i return False idea 2: dichotomy def reduce_inter (nums2, left) Right): "mid = (left + right) / / 2 count = 0 length = len (nums2) for i in range (length): if (nums2 [I] > = left) and (nums2 [I] mid-left + 1: return left, mid else: return mid+1, rightdef find_duplicated_num2 (nums2): left, right = 1, len (nums2)-1 while left! = right: left Right = reduce_inter (nums2, left, right) return left Test nums = [2, 3, 5, 4, 3, 2, 6, 7] # nums_n = [5, 4, 3, 2, 6, 7] print ("idea 1 Test results:", find_duplicated_num (nums)) print ("idea 2 Test results:", find_duplicated_num2 (nums))

Result

Train of thought 1 Test results: 3

Train of thought 2 Test results: 3

The above is about "Python does not modify the array how to find duplicate numbers" of this article, I believe we all have a certain understanding, I hope the editor to share the content to help you, if you want to know more related knowledge, please pay attention to the industry information channel.

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.