[Code] refers to the repeated number in the offer 03 array

Catalog

1、 subject

2、 Problem solving

3、 Reference resources

---

1、 subject

Find the repeated numbers in the array .

At a length of n Array of nums All the numbers in 0～n-1 Within the scope of . Some numbers in the array are repeated , But I don't know how many numbers are repeated , I don't know how many times each number has been repeated . Please find any duplicate number in the array .

Example 1：

Input ：
[2, 3, 1, 0, 2, 5, 3]
Output ：2 or 3 

2、 Problem solving

The key to this question is to find 【 arbitrarily 】 A repeat Numbers that will do

Ideas ： Hashtable / Set（ Essentially a one-dimensional array ）
Using the characteristics of data structure , Easy to think of Use hash table （Set） Record the numbers of the array , When a duplicate number is found, it returns directly .

Algorithm flow ：
initialization ： newly build HashSet , Write it down as dict ;
Traversal array nums Every number in n ：
When n stay dict in , Repeated description , Go straight back to Numbers n ;
Otherwise it would be Figures that have never appeared n Added to the dict in ;
 

Complexity analysis ：

• Time complexity O(N)： Traverse Using an array O(N) ,HashSet Add and find All elements are O(1) .
• Spatial complexity O(N) ： HashSet Occupy O(N) The size of the extra space （ Additional space requested ）.

Here is K God explains the problem-solving ideas in detail  

def findRepeatNumber(nums):
    dict = set()
    for n in nums:
        if n in dict:
            return n
        else:
            dict.add(n)


nums = [2, 3, 1, 0, 2, 5, 3]
result = findRepeatNumber(nums)
print(result)

arr = input("please input some numbers with blank")    
nums2 = [int(n) for n in arr.split()] 
result2 = findRepeatNumber(nums2)
print(result2)

result

   
2
please input some numbers with blank
2 3 1 0 2 5 3
2


** Process exited - Return Code: 0 **
Press Enter to exit terminal

Advanced thinking  

The above method space complexity is O(N), Is there any way to reduce ？

 

In situ exchange

The title description has not been fully used , namely At a length of n Array of nums All the numbers in 0 ~ n-1 Within the scope of . This description means ： Of array elements Indexes and value yes One to many The relationship between .

therefore , The array can be traversed and exchanged , Make the element Indexes And value One-to-one correspondence （ namely nums[i]=i ）. thus , You can map the corresponding value through the index , Play a role equivalent to a dictionary .

That is, on the basis of the original array, make the index and the corresponding value of the index equal , The index is 0, The value is 0, The index is 1, The value is 1.

Algorithm flow ：( The key is conditional judgment ）
Traversal array nums , Let the initial value of index be n=0 :

if nums[n] =n ： Indicates that this number is already in the corresponding index position , There is no need to exchange , So skip , Continue to traverse and execute ;
if nums[nums[n]] =nums[n] ： For index nums[n] Place and index n The element values at are nums[n] , That is, find a set of duplicate values , Return this value nums[n] ;
otherwise ： The exchange index is i and nums[n] The element value of , Exchange this number to the corresponding index position .

Complexity analysis ：
Time complexity O(N)： Traverse Using an array O(N) , Judgment and exchange of each round of traversal Operation and use O(1) .
Spatial complexity O(1) ： Use the extra space of constant complexity .

Code

def findRepeatNumber(nums):
    n = 0
    while n < len(nums):
        if nums[n] == n:
            n += 1
            continue
        if nums[nums[n]] == nums[n]:
            return nums[n]
        else:
            nums[nums[n]], nums[n] =  nums[n], nums[nums[n]]
        

        
nums = [2, 3, 1, 0, 2, 5, 3]
result = findRepeatNumber2(nums)
print(result)

arr = input("please input some numbers with blank")    
nums2 = [int(n) for n in arr.split()] 
result2 = findRepeatNumber(nums2)
print(result2)

result  

   
2
please input some numbers with blank
2 3 1 0 2 5 3
2


** Process exited - Return Code: 0 **
Press Enter to exit terminal

3、 Reference resources

2022 How to prepare for the algorithm post ？ - You know

2023 Summary of the knowledge of the school recruitment algorithm post - You know

Machine learning interview preparation

GitHub - rushter/MLAlgorithms: Minimal and clean examples of machine learning algorithms implementations 【 The finger of the sword offer】 high frequency ML/DL Interview questions （ Continuous updating ）_ Mountaintop evening view blog -CSDN Blog [email protected]GitHub - scutan90/DeepLearning-500-questions: Deep learning 500 ask , The common probability knowledge in the form of question and answer 、 linear algebra 、 machine learning 、 Deep learning 、 Computer vision and other hot issues , To help yourself and readers in need . The book is divided into 18 Chapters ,50 More than ten thousand words . Due to limited level , The readers are kindly requested to criticize and correct the improper parts in the book . To be continued ............ If you want to cooperate , contact [email protected] copyright , Violation of rights will be prosecuted Tan 2018.06GitHub - geektutu/interview-questions: machine learning / Deep learning /Python/Go Language interview questions pen test questions (Machine learning Deep Learning Python and Golang Interview Questions)GitHub - amusi/Deep-Learning-Interview-Book: Deep learning interview guide （ Including mathematics 、 machine learning 、 Deep learning 、 Computer vision 、 Natural language processing and SLAM Wait for the direction ）

Online Python - IDE, Editor, Compiler, Interpreter

jyd - Power button （LeetCode）

GitHub - krahets/LeetCode-Book: 《 The finger of the sword Offer》 Python, Java, C++ Solution code ,LeetBook《 Graphical algorithm data structure 》 Supporting code warehouse .

GitHub - Jack-Cherish/LeetCode: LeetCode、 The finger of the sword Offer Brush notes （C/C++、Python3 Realization ）

GitHub - greyireland/algorithm-pattern: Algorithm template , The most scientific way to brush questions , The fastest way to brush questions , You deserve it ~ GitHub - zhulintao/CodingInterviewChinese2: 《 The finger of the sword Offer》 The second version of source code （Clone from: https://github.com/zhedahht/CodingInterviewChinese2）