Sword finger offer day 4 (Sword finger offer 03. duplicate numbers in the array, sword finger offer 53 - I. find the number I in the sorted array, and the missing numbers in sword finger offer 53 - ii

The finger of the sword Offer 03. Repeated numbers in an array

Title Description

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 

Be careful

When no result is returned , Need to return null value

Code

c++ edition

class Solution {
    
public:
    int findRepeatNumber(vector<int>& nums) {
    
        int n = nums.size();
        map<int,int> mp;
        int t = -1;
       for(int i=0;i<n;i++){
    
            if(mp[nums[i]]){
    
                t = nums[i];
                break;
            }else{
    
                mp[nums[i]]=1;
            }
        }
        if(t!=-1)return t;
        else{
    
            return {
    {
    }};
        }
    }
};

The finger of the sword Offer 53 - I. Look up numbers in the sort array I

Title Description

Count the number of times a number appears in the sort array .

Example 1

 Input : nums = [5,7,7,8,8,10], target = 8
 Output : 2

Example 2

 Input : nums = [5,7,7,8,8,10], target = 6
 Output : 0

Code

c++ edition

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    
        int n = nums.size();
        int f = 0;
        for(int i=0;i<n;i++){
    
            if(nums[i]==target){
    
                f++;
            }
        }
        return f;
    }
};

python edition

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = 0
        for i in range(n):
            if nums[i]==target :
                f = f+1
        return f

The finger of the sword Offer 53 - II. 0～n-1 Missing numbers in

Title Description

A length of n-1 All numbers in the incremental sort array of are unique , And every number is in the range 0～n-1 within . In scope 0～n-1 Internal n There are and only one number is not in the array , Please find out the number .

Example 1

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

Example 2

 Input : [0,1,2,3,4,5,6,7,9]
 Output : 8

Code

c++ edition

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int n = nums.size();
        int f = -1;
        int vis[10010]={
    0};
        for(int i=0;i<n;i++){
    
            vis[nums[i]] = 1;
        }
        //return n;
        for(int i=0;i<=n;i++){
    
            if(!vis[i]){
    
                f = i;
            }
        }
        return f;
    }
};

python edition

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        vis = [0]*10010
        n = len(nums)
        for i in range(n):
            vis[nums[i]] = 1
        for i in range(n+1):
            if not vis[i] :
                return i

---

If this article is helpful to my friends , I hope you can give me some praise and support ~ Thank you very much. ~

---