287 finding duplicates

One 、 Preface

label ： Two points search .

Source of problem LeetCode 287 difficulty ： secondary .

Question link ：https://leetcode-cn.com/problems/find-the-duplicate-number/

 

Two 、 subject

Given an inclusion  n + 1 Array of integers  nums, The numbers are all in 1 To n  Between （ Include 1 and n）, We know that there is at least one duplicate integer . Let's say there's only one repeating integer , Find out the number of repetitions .

Example 1:

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

Example 2:

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

explain ：

 You cannot change the original array （ Suppose the array is read-only ）.
 Only use the extra  O(1)  Space .
 Time complexity is less than  O(n2) .
 There is only one duplicate number in the array , But it may appear more than once .

 

3、 ... and 、 Ideas

The space complexity required by the topic is O(1), Without this requirement , One traversal is enough . To meet the requirements , Look at the title again ,[ Given an inclusion  n + 1 Array of integers  nums, The numbers are all in 1 To n  Between （ Include 1 and n）, We know that there is at least one duplicate integer . Let's say there's only one repeating integer , Find out the number of repetitions ], The first time I looked at the question, I swept over and didn't understand the meaning of the question correctly .

1. According to the meaning of the title, it is an array a[i],1 <= i <= n && 1 <= a[i] <=n, One and only one number appears many times . That can be changed a[i] Record Numbers i Number of occurrences , Now we need to find k Need to meet a[k] > 1.
2. We are 1-n Choose any value between m,k Included in [1,m] Or included in [m+1,n] Between , It doesn't matter which one is included , If included in [1,m], that sum(a[1,m]) > m, On the contrary, it is contained in [m+1,n] Between .
3. Pass step 2, We can shrink k Range , Always follow the steps 2, Until the interval cannot be narrowed , You can be sure k The value of .

For reducing the interval in step 2, you can use Dichotomy search , Next, we need to prove ： If included in [1,m], that sum(a[1,m]) > m

prove ,k Included in [i,m],sum(a[1,m]) > m.

1. hypothesis a[k] = 2, Well, except a[k] All other numbers appear once , be sum(a[1,m]) = m+1, Satisfy sum(a[1,m]) > m
2. hypothesis a[k] = 3, Well, except a[k] There will be a number outside 0 Time , If appear 0 The number of times is greater than m, be sum(a[1,m]) = m+2, Satisfy sum(a[1,m]) > m; If appear 0 The number of times is not greater than m, be sum(a[1,m]) = m+1, Satisfy sum(a[1,m]) > m. The final result meets sum(a[1,m]) > m
3. hypothesis a[k] > 3, Well, except a[k] There will be multiple numbers outside 0 Time , If appear 0 No more than m, be sum(a[1,m]) = m+2, Satisfy sum(a[1,m]) > m; If there is h Number appears 0 The number of times is greater than m, be sum(a[1,m]) = m+1 + h, Satisfy sum(a[1,m]) > m. The final result meets sum(a[1,m]) > m
4. therefore a[k] > 2, Satisfy k Included in [i,m],sum(a[1,m]) > m

 

Four 、 summary

• Meaning of the title [ Given an inclusion  n + 1 Array of integers  nums, The numbers are all in 1 To n  Between （ Include 1 and n）] Need to see clearly , On the importance of reading questions hahaha .
• This question skillfully uses the rules in the meaning of the question .

 

5、 ... and 、 coded

//==========================================================================
/*
* @file    : 287_FindDuplicate.h
* @label   :  Two points search 
* @blogs   : https://blog.csdn.net/nie2314550441/article/details/107586568
* @author  : niebingyu
* @date    : 2020/07/25
* @title   : 287. Look for repetitions 
* @purpose :  Given an inclusion  n + 1  Array of integers  nums, The numbers are all in  1  To  n  Between （ Include  1  and  n）,
*  We know that there is at least one duplicate integer . Let's say there's only one repeating integer , Find out the number of repetitions .
*
*  Example  1:
*    Input : [1,3,4,2,2]
*    Output : 2
*
*  Example  2:
*    Input : [3,1,3,4,2]
*    Output : 3
*
*  explain ：
*    You cannot change the original array （ Suppose the array is read-only ）.
*    Only use the extra  O(1)  Space .
*    Time complexity is less than  O(n2) .
*    There is only one duplicate number in the array , But it may appear more than once .
*
*  source ： Power button （LeetCode）
*  difficulty ： secondary 
*  link ：https://leetcode-cn.com/problems/find-the-duplicate-number/
*/
//==========================================================================
#pragma once
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <assert.h>
using namespace std;

#define NAMESPACE_FINDDUPLICATE namespace NAME_FINDDUPLICATE {
#define NAMESPACE_FINDDUPLICATEEND }
NAMESPACE_FINDDUPLICATE

class Solution 
{
public:
    int findDuplicate(vector<int>& nums) 
    {   
        int n = nums.size();
        int l = 1, r = n - 1, ans = -1;

        while (l <= r) 
        {
            int mid = (l + r) >> 1;  
            int cnt = 0;
            for (int i = 0; i < n; ++i) 
            {
                // Traversal array   If the value in the array   Less than mid  Add up bool value   To cnt in 
                cnt += nums[i] <= mid;
            }

            // If after accumulation   Small is equal to  mid  The number of   Small is equal to  mid  
            // That means   Array   Small is equal to mid It's worth it   Elements   There is no repetition 
            // Update left border 
            if (cnt <= mid) 
                l = mid + 1; 
            // Otherwise, explain   There are repeating elements 
            else 
            {
                r = mid - 1; // Update right border 
                ans = mid; // And save the current  mid value   Because the current mid It could be a repeating element 
            }
        }
        return ans;
    }
};

 Here is the test code //
//  test   Use cases  START
void test(const char* testName, vector<int>& nums, int expect)
{
    Solution s;
    int result = s.findDuplicate(nums);

    if (result == expect)
        cout << testName << ", solution passed." << endl;
    else
        cout << testName << ", solution failed. " << endl;
}

//  The test case 
void Test1()
{
    vector<int> nums = { 1,3,4,2,2 };
    int expect = 2;
    test("Test1()", nums, expect);
}

NAMESPACE_FINDDUPLICATEEND
//  test   Use cases  END
//
void FindDuplicate_Test()
{
    cout << "------ start 287. Look for repetitions  ------" << endl;
    NAME_FINDDUPLICATE::Test1();
    cout << "------ end 287. Look for repetitions  --------" << endl;
}

Execution results ：