哈希表刷题(下)

一、缺失的第一个正整数

该题存在问题，除解法一，解法四外，其他解法适用于无重复元素

解法一:哈希表(推荐)

• 用unordered_map创建一个哈希表，记录数组中出现的数字
• 从1开始遍历到n，查询哈希表是否有有此数字，没有它即时数组第一个缺失的正整数
• 如果遍历到最后都找到了，则确实第n+1个

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]]++;//记录出现的数据
        int pos=1;
        while(um.find(pos)!=um.end())
            pos++;
        return pos;
    }
};

时间复杂度：O(n)，第一次遍历数组，为O(n)，第二次最坏从1遍历到n，为O(n)
空间复杂度：O(n)，哈希表记录n个不重复的元素，长度为n

解法二:原地哈希

• 先遍历数组将所有负数修改为n+1
• 再次遍历数组，当遇到的数的绝对值不超过n时，则表示该元素位1~n里的元素，将该数值对应的下标里的元素改为负数，相当于出现过的正整数的下标都指向一个负数，这是类似哈希表的实现原理的操作
• 最后遍历数组，遇到的第一个非负下标即为缺失正整数

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;//负数标记为n+1
        for(int&i:nums)
            if(abs(i)<=n)
                nums[abs(i)-1]=-1*abs(nums[abs(i)-1]);//将该数字的下标标记为负数
        for(int i=0;i<n;i++)
            if(nums[i]>0)//找到第一个不为负的下标
                return i+1;
        return n+1;
    }
};

时间复杂度：O(n)，多次遍历数组，都是单层循环
空间复杂度：O(1)，原地哈希，以索引为指向，没有额外空间

解法三:排序

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)//负数统计其个数
                ct1++;
            else if(i!=++ct2)//是正整数则从一开始找，不匹配的即为缺失值
                return ct2;
        }
        return n-ct1+1;
    }
};

时间复杂度:O(n${\log }_2$n),排序
空间复杂度：O(1)

解法四:二分查找

class Solution {
    
public:
	int binarysearch(vector<int>&v,int target){
    //在给定区间内二分查找
		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());//排序
		for(int i=1;i<=n;i++){
    //对1~n所有元素依次使用二分查找
			if(binarysearch(nums,i)==-1)return i;//找不到说明出现次数为1
		} 
		return n+1;//若从1到遍历n，这n个正整数都存在，则正整数n+1一定不存在
    }
};

时间复杂度:O(n${\log }_2$n),排序
空间复杂度：O(1)

二、三数之和

解法一:暴力法

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
                continue;
            for(int j=i+1;j<n;j++)//不重复当前数+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;    
    }
};

时间复杂度：O(n${\log }_2$n) +O(n^3);排序算法O(n${\log }_2$n)+三重循环枚举
空间复杂度：O(1);数组存储与读取数据

解法二:双指针(推荐)

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)//若指针l,r加当前数i等于0，则找到答案
                {
    
                    result.push_back({
    num[i],num[l],num[r]});
                    while(num[l]==num[l+1]&&l+1<r)//判断指针指向是否重复，重复跳过
                        l++;
                    while(num[r]==num[r-1]&&r-1>l)
                        r--;
                    l++,r--;
                }
                else if(num[l]+num[r]+num[i]>0)//较大，缩减右区间
                    r--;
                else//反之缩减左区间
                    l++;
            }
        }
        return result;
    }
};

时间复杂度：O(n${\log }_2$n) + O(n^2),排序算法O(n${\log }_2$n)+双指针
空间复杂度：O(1)