Hash table questions (Part 2)

One 、 Missing first positive integer

There is a problem with this question , Division solution one , Solution four sides , Other solutions apply to non repeating elements

Solution 1 : Hashtable ( recommend )

• use unordered_map Create a hash table , Record the numbers that appear in the array
• from 1 So let's start walking through n, Query whether the hash table has this number , Without it, the first missing positive integer in the array
• If the traversal finally finds , Then it is true that n+1 individual

class Solution {
    
public:
    int minNumberDisappeared(vector<int>& nums) {
    
        // write code here
        int n=nums.size();
        unordered_map<int,int>um;
        for(int i=0;i<n;i++)
            um[nums[i]]++;// Record the data that appears 
        int pos=1;
        while(um.find(pos)!=um.end())
            pos++;
        return pos;
    }
};

Time complexity ：O(n), Traversing the array for the first time , by O(n), The second worst is from 1 Traversing n, by O(n)
Spatial complexity ：O(n), Hash table records n A non repeating element , The length is n

Solution 2 : In situ hash

• First traverse the array and change all negative numbers to n+1
• Traversal array again , When the absolute value of the number encountered does not exceed n when , Indicates the element bit 1~n Elements in , Change the element in the subscript corresponding to this value to a negative number , It is equivalent that the subscripts of positive integers that have appeared point to a negative number , This is an operation similar to the implementation principle of hash table
• Finally, we traverse the array , The first non negative subscript encountered is the missing positive integer

class Solution {
    
public:
    int minNumberDisappeared(vector<int>& nums) {
    
        // write code here
        int n=nums.size(); 
        for(int&i:nums)
            if(i<=0)
                i=n+1;// Negative numbers are marked n+1
        for(int&i:nums)
            if(abs(i)<=n)
                nums[abs(i)-1]=-1*abs(nums[abs(i)-1]);// Mark the subscript of the number as negative 
        for(int i=0;i<n;i++)
            if(nums[i]>0)// Find the first non negative subscript 
                return i+1;
        return n+1;
    }
};

Time complexity ：O(n), Traverse the array many times , It's all single-layer circulation
Spatial complexity ：O(1), In situ hash , Point to the index , There is no extra space

Solution 3 : Sort

class Solution {
    
public:
    int minNumberDisappeared(vector<int>& nums) {
    
        // write code here
        sort(nums.begin(),nums.end());
        int n=nums.size(),ct1=0,ct2=0;
        for(int&i:nums)
        {
    
            if(i<=0)// Negative numbers count their numbers 
                ct1++;
            else if(i!=++ct2)// If it is a positive integer, find it from the beginning , What does not match is the missing value 
                return ct2;
        }
        return n-ct1+1;
    }
};

Time complexity :O(n${\log }_2$n), Sort
Spatial complexity ：O(1)

Method four : Two points search

class Solution {
    
public:
	int binarysearch(vector<int>&v,int target){
    // Binary search in a given interval 
		int l=0,r=v.size()-1;
		while(l<=r){
    
			int mid=l+(r-l)/2;
			if(v[mid]==target)
                return mid;
			else if(v[mid]<target)
                l=mid+1;
			else 
                r=mid-1; 
		}
        return -1;
	}
    int minNumberDisappeared(vector<int>& nums) {
    
	    int n=nums.size();
	    sort(nums.begin(),nums.end());// Sort 
		for(int i=1;i<=n;i++){
    // Yes 1~n All elements use binary search in turn 
			if(binarysearch(nums,i)==-1)return i;// The number of occurrences of the description that cannot be found is 1
		} 
		return n+1;// If from 1 To traverse n, this n All positive integers exist , Then positive integer n+1 It must not exist 
    }
};

Time complexity :O(n${\log }_2$n), Sort
Spatial complexity ：O(1)

Two 、 Sum of three numbers

Solution 1 : Violence law

class Solution {
    
public:
    vector<vector<int> > threeSum(vector<int> &num) {
    
        vector<vector<int>>result;
        int n=num.size();
        if(n<3)
            return result;
        sort(num.begin(),num.end());// Make the result ascending 
        for(int i=0;i<n-2;i++)
        {
    
            if(i&&num[i]==num[i-1])// If the current number of the loop is the same as before continue
                continue;
            for(int j=i+1;j<n;j++)// Do not repeat the current number +1
            {
    
                if(j>i+1&&num[j]==num[j-1])
                    continue;
                for(int k=j+1;k<n;k++)
                {
    
                    if(k>j+1&&num[k]==num[k-1])
                        continue;
                    if(num[i]+num[j]+num[k]==0)
                        result.push_back({
    num[i],num[j],num[k]});
                }
            }
        }
        return result;    
    }
};

Time complexity ：O(n${\log }_2$n) +O(n^3); Sorting algorithm O(n${\log }_2$n)+ Triple loop enumeration
Spatial complexity ：O(1); Array storage and reading data

Solution 2 : Double pointer ( recommend )

class Solution {
    
public:
    vector<vector<int> > threeSum(vector<int> &num) {
    
        vector<vector<int>>result;
        int n=num.size();
        if(n<3)
            return result;
        sort(num.begin(),num.end());
        for(int i=0;i<n-2;i++)
        {
    
        if(i&&num[i]==num[i-1])
            continue;
            int l=i+1,r=n-1;
            while(l<r)
            {
    
                if(num[l]+num[r]+num[i]==0)// If pointer l,r Add the previous number i be equal to 0, Then find the answer 
                {
    
                    result.push_back({
    num[i],num[l],num[r]});
                    while(num[l]==num[l+1]&&l+1<r)// Judge whether the pointer points to repetition , Repeat skip 
                        l++;
                    while(num[r]==num[r-1]&&r-1>l)
                        r--;
                    l++,r--;
                }
                else if(num[l]+num[r]+num[i]>0)// more , Reduce the right interval 
                    r--;
                else// Conversely, reduce the left interval 
                    l++;
            }
        }
        return result;
    }
};

Time complexity ：O(n${\log }_2$n) + O(n^2), Sorting algorithm O(n${\log }_2$n)+ Double pointer
Spatial complexity ：O(1)