Single Number II--LeetCode

我会带着你远行 2022-08-05 13:24 8阅读 0赞

# 题目： #

Given an array of integers, every element appears three times except for one. Find that single one.

Note:  
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路：可以为这个数组分类，对于一个整数，遍历每一位，既然是三个都是一样的，如果某一位出现分歧，那么一个数组的个数肯定是3的倍数，另一个是3的倍数多1，知道一个数组中只有一个数，就是目标

时间复杂度也是0（n） 准确的说是O（32\*n）

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    /*
    一个数组中只有一个数出现了一次 其他都是出现三次 找出这个数 
    */
    
    // 根据位来判断
    
    int SingleNumberII(vector<int>& vec)
    {
    	int i,j;
    	int low=0,high = vec.size()-1;
    	int bit =1;
    	int flag=0;
    	while(low <=high)
    	{
    	
    		if(low == high)
    			return vec[low];
    		i = low-1;
    		for(j=low;j<=high;j++)
    		{
    			if((vec[j]&bit) == 0)
    			{
    				i++;
    				swap(vec[i],vec[j]);
    			}
    		}
    		if(i >=low)
    		{
    			if((i-low+1)%3==0)
    				low = i+1;
    			else
    				high = i;
    		}
    		bit = bit<<1;
    	}
    	return 0;
    } 
    
    int main()
    {
    	
    	vector<int> vec;
    		vec.push_back(54);
    	
    	
    	vec.push_back(96);
    	vec.push_back(54);
    	vec.push_back(54);
    	
    	vec.push_back(123);
    	vec.push_back(123);
    	vec.push_back(123);
    	
    	vec.push_back(345);
    	vec.push_back(345);
    	vec.push_back(345);
    	
    
    	
    	vec.push_back(67);
    	vec.push_back(67);
    	vec.push_back(67);
    	
    	vec.push_back(87);
    	vec.push_back(87);
    	vec.push_back(87);
    	
    	
    	cout<<SingleNumberII(vec)<<endl;
    	return 0;
    }

上述这种思路也是可以解决问题的，就是使用快速排序的思想使得这个数组按照某一个位来划分，对于任何一个位， 为0或者为1的个数都是3的倍数。  
第二种方法就是也是使用位的方法，我们遍历所有数的每一位，发现某个位不是1就是0，如果为1的个数不是3的倍数，那么这个数就是需要求的数的相应位的值，这个时间复杂度为0(32\*n),也可以看成是常数的时间复杂度。