精华内容
下载资源
问答
  • 数组中唯一只出现一次的数字 在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。 请找出那个只出现一次的数字。 你可以假设满足条件的数字一定存在。 思考题: 如果要求只使用 O(n) 的时间和额外 O(1)...

    数组中唯一只出现一次的数字

    在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。

    请找出那个只出现一次的数字。

    你可以假设满足条件的数字一定存在。

    思考题:

    如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

    样例
    输入:[1,1,1,2,2,2,3,4,4,4]
    输出:3
    

    数学

    时间复杂度O(n)

    class Solution {
        public int findNumberAppearingOnce(int[] nums) {
            int[] sums = new int[32];
            for(int num :nums){
                for(int i = 0;i < 32;i++){
                    int temp = num >> i & 1;
                    sums[i] += temp;
                }
            }
            int res = 0;
            for(int i = 0; i< 32;i++){
                res += (sums[i] % 3) == 0 ? 0 : 1 << i;
            }
            return res;
        }
    }
    
    展开全文
  • 题目  一个整型数组里除了两个数字...也就是说, 如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次的数字,因为那些成对出现两次的数字全部在或中抵消了。  2.把原数组分成两个...

    题目

      一个整型数组里除了两个数字之外,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n),空间复杂度是 O(1)。

    思路

      1.异或运算的一个性质:任何一个数字异或它自己都等于 0。也就是说, 如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次的数字,因为那些成对出现两次的数字全部在或中抵消了。

      2.把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字,而其他数字都成对出现两次。如果能够这样拆分成两个数组, 我们就可以按照前面的办法分别找出两个只出现一次的数字了。

      3.我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次,在异或中全部抵消了。由于这两个数字肯定不一样,那么异或的结果肯定不为 0,也就是说在这个结果数字的二进制表示中至少就有一位为 1 。我们在结果数字中找到第一个为 1 的位的位置,记为第 n 位。现在我们以第 n 位是不是 1 为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第 n 位都是 1,而第二个子数组中每个数字的第 n 位都是 0。由于我们分组的标准是数字中的某一位是 1 还是 0 , 那么出现了两次的数字肯定被分配到同一个子数组。因为两个相同的数字的任意一位都是相同的,我们不可能把两个相同的数字分配到两个子数组中去,于是我们已经把原数组分成了两个子数组,每个子数组都包含一个只出现一次的数字,而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次数字, 因此到此为止所有的问题都已经解决了。

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution
    {
        public:
            void find_appear_once(vector<int> &v);
            int find_first_bit_1(int res);
            bool is_bit_1(int n,int index);
    };
    void Solution::find_appear_once(vector<int> &v)
    {
        if(v.empty()||v.size()<2)
            return ;
            
        int result=0;
        for(auto k:v)
            result^=k;
        int index=find_first_bit_1(result);
        
        int res1=0,res2=0;
        for(auto k:v)
        {
            if(is_bit_1(k,index))
                res1^=k;
            else
                res2^=k;
        }
        cout<<res1<<'\t'<<res2<<endl;
    }
    int Solution::find_first_bit_1(int res)
    {
        int index=0;
        while(((res&1)==0)&&index<8*sizeof(int))
        {
            res>>=1;
            ++index;
        }
        return index;
    }
    bool Solution::is_bit_1(int n,int index)
    {
        n>>=index;
        return n&1;
    }
    int main()
    {
        vector<int> v{2,4,3,6,3,2,5,5};
        Solution s;
        s.find_appear_once(v);
        return 0;
    }

     题目

      在一个数组中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

    思路 

    一: 

     一个数字的二进制表示中有些位为 0,有些位为 1。因此如果这个数字出现 3 次,假如我们使用某个位数组记录每一位的和,那么这个位数组中的每个数都能够整除 3。所以这个思路是:使用一个数组记录每个数字的二进制表示中位的和,把数组中所有的数字按位相加并将结果存到位数组中,然后把位数组中的每个数值整除 3,如果能够整除,说明只出现一次的数字在该位上等于 0,否则等于 1,最终还原数字即可。这个算法的时间复杂度是 O(n);只需要一个容量位 32 的数组,空间复杂度是 O(1)。

    二:

      同样从位运算的角度来看,我希望一个数用来表示出现一次的位,也就是说这个数的为1的位就表示这个位上面的数出现过了一次,比如0x10001,就表示bit[0]和bit[4]就是出现过了一次的位。然后再用一个数表示出现过了两次的位,再用一个数表示出现过了3次的位。只要这个位出现过了3次,我就把这个位拿清除掉,这样剩余的最后出现过一次的位的这个数就是我们要找的数了。

    1.

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution
    {
        public:
            void find_appear_once(const vector<int> &v);
    };
    void Solution::find_appear_once(const vector<int> &v)
    {
        if(v.empty()||v.size()<=0)
            return ;
    
        vector<int> bit_sum(32,0);
        for(int i=0;i<v.size();++i)
        {
            int bit_mask=1;
            for(int j=31;j>=0;--j)//每个数都从最低位开始判断
            {
                int t=v[i]&bit_mask;
                if(t)
                    bit_sum[j]+=1;
                bit_mask<<=1;
            }
        }
        int res=0;
        for(int i=0;i<bit_sum.size();++i)
        {
            res<<=1;//先把当前结果左移到高位
            res+=bit_sum[i]%3;//然后把当前位应该为0还是1填上去
        }
        cout<<res<<endl;
    }
    int main()
    {
        Solution s;
        vector<int> v{2,3,3,3,5,5,5};
        s.find_appear_once(v);
        return 0;
    }

    2.

    class Solution {
    public:
        int singleNumber(int A[], int n) {
            int ones = 0;
            int twos = 0;
            int threes = 0;
            int i = 0;
            
            for(i = 0; i < n; i++){
                twos |= ones & A[i];
                ones ^= A[i];
                threes = ones & twos;
                ones &= ~threes;
                twos &= ~threes;
            }
            return ones;
        }
    };

     

    转载于:https://www.cnblogs.com/tianzeng/p/10294216.html

    展开全文
  • 此题是求数组中唯一只出现一次的数字,其他数字均出现了三次 /** *Copyright @ 2019 Zhang Peng. All Right Reserved. *Filename: *Author: Zhang Peng *Date: *Version: *Description: **/ #include<...

    此题是求数组中唯一只出现一次的数字,其他数字均出现了三次

    /**
     *Copyright @ 2019 Zhang Peng. All Right Reserved.
     *Filename:
     *Author: Zhang Peng
     *Date:
     *Version:
     *Description:
    **/
    
    #include<iostream>
    #include<vector>
    using namespace std;
    
    int FindOnlyNum(vector<int> data)
    {
    	int bitcount[32] = {0};
    	//记录各二进制位数上1出现的次数
    	for (int i = 0; i < data.size(); i++)
    	{
    		int v = data[i];
    		int index = 1;
    		for (int j = 31; j >=0; j--)
    		{
    			int num = index&v;
    			if (num != 0)
    				bitcount[j] += 1;
    			index=index << 1;
    		}
    	}
    
    	//将各位整除3以后余下的个数组合在一起
    	int result = 0;
    	for (int k = 0; k < 32; k++)
    	{
    		result = result << 1;
    		result += bitcount[k] % 3;
    	}
    
    	return result;
    }
    
    int main()
    {
    	vector<int> data = { 1, 2, 3, 4, 1, 1, 2, 2, 4, 4 };
    	cout << FindOnlyNum(data) << endl;
    
        system("pause");
        return 0;
    }
    
    
    展开全文
  • 数组中唯一只出现一次的数字-56-2 在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。 请找出那个只出现一次的数字。 你可以假设满足条件的数字一定存在。 思考题: 如果要求只使用 O(n) 的时间和...

    数组中唯一只出现一次的数字-56-2

    在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。

    请找出那个只出现一次的数字。

    你可以假设满足条件的数字一定存在。

    思考题:

    • 如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

    样例

    输入:[1,1,1,2,2,2,3,4,4,4]
    输出:3
    

    思路:

    统计数组中所有数字的各个位之和,若 bit[i] % 3 != 0,说明只出现一次的数字的这一位是 1,否则这一位是 0 。循环遍历,即可得出结果。

    class Solution {
        public int findNumberAppearingOnce(int[] nums) {
            int res = 0;
            for(int i = 0; i < 32; i++){
                int bitsum = 0;
                int bit = 1 << i;
                for(int num : nums){
                    if((num & bit) != 0) bitsum++;
                }
                if(bitsum % 3 != 0) res |= bit;
            }
            return res;
        }
    }
    
    展开全文
  • 数组中唯一只出现一次的数字,其他都是3次。 eg:{2,2,4,2}结果是4. 思路:剑指offer 位运算 * 如果一个数字出现三次,那么它对应的二进制表示的每一位都出现了三次。 将数组中所有数字的二进制表示的每一位都加起来...
  • 这里是题目描述:剑指Offer-面试题56-II:数组中唯一只出现一次的数字 本题可以用哈希表统计数组中每个数字出现次数,时间复杂度O(n),空间复杂度O(n)。我们可以使用位运算的方法,将空间复杂度降至O(1)——统计数组...
  • // 面试题56(二):数组中唯一只出现一次的数字 // 题目:在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。请 // 找出那个吃出现一次的数字。 #include <iostream> int ...
  • 数组中唯一只出现一次的数字 在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。 请找出那个只出现一次的数字。 你可以假设满足条件的数字一定存在。 思考题: 如果要求只使用 O(n) 的时间和额外 O(1...
  • (C++)剑指offer-拓展:数组中唯一只出现一次的数字 首先将数组中每个数字进行二进制表示,这样便可以统计每个位上对应1的次数,如果次数%3多1,则说明唯一出现一次的数字在该二进制位为1,因此记录到ans结果中并移...
  • 请找出那个只出现一次的数字。 思路:我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1。 代码如下: #include&...
  • 请找出那个只出现一次的数字。你可以假设满足条件的数字一定存在。 思考题: 如果要求只使用 O(n)的时间和额外 O(1)的空间,该怎么做呢? 样例 输入:[1,1,1,2,2,2,3,4,4,4] 输出:3 分析: 方法一: 统计...
  • 请找出那个只出现一次的数字。 这题有点意思,其他数字都重复了三次,一般位运算就消不掉了。 解题思路 将所有数字的二进制表示的对应位都加起来,如果某一位能被三整除,那么只出现一次的数字在该位为0;反之,...
  • 题目: ...统计二进制每一位的和,如果该位的和对3取余不为0,则表示这个只出现一次的数字该位为1 代码实现: class Solution { public: int singleNumber(vector<int>& nums) { ...
  • 请找出那个只出现一次的数字。 思路:我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1。 代码如下: int ...
  • 请写程序找出这两个只出现一次的数字。 思路: 1. 从头到尾依次异或数组中的每个数字,找到结果数字中第一个为1的位置,记为第n位。 2.以第n位是不是1为标准把原数组中的数字分成两个数组,第一个子数组中每个...
  • 请找出那个只出现一次的数字。 你可以假设满足条件的数字一定存在。 思考题: 如果要求只使用O(n) 的时间和额外O(1) 的空间,该怎么做呢? 样例 输入:[1,1,1,2,2,2,3,4,4,4] 输出:3 问题分析 先将数组中的...
  • 请找出那个只出现一次的数字。 2.解题思路 将所有出现三次数字的二进制表示的对应位都加起来,每一位的和都能被3整除。将所有数字的二进制表示的对应位都加起来,如果某一位能被三整除,那么只出现一次的数字在该...
  • 题目:在一个数组中除一个数字只出现一次以外,其他数字都出现了3次。请找出这个数字 思路: 首先看看题目要求: 数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次。请给出最快方法找到x。...
  • 请找出那个只出现一次的数字。 解题思路 位运算 如果一个数字出现3次,那它的二进制对应的每一位(0或者1)也出现三次,将他们累加,则一定可以被3整除。 因此,累加后的和能被3整除,那只出现一次的数字二进制对应...
  • 请找出那个只出现一次的数字。你可以假设满足条件的数字一定存在。 思考题: 如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢? 样例 输入:[1,1,1,2,2,2,3,4,4,4] 输出:3 (理解起来还挺困难啊!)...
  • 如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示对应的那一位是0;否则就是1。这种解法的时间效率是O(n)。我们需要一个长度为32的辅助数组存储二进制表示的每一位的和。由于数组的长度是固定的,...
  • 请找出那个只出现一次的数字 [牛客网刷题地址]无 思路分析  如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的...
  • 请找出那个只出现一次的数字。 思路  这道题中数字出现了三次,无法像56-1) 数组中只出现一次的两个数字一样通过利用异或位运算进行消除相同个数字。但是仍然可以沿用位运算的思路。  将所有数字的二进制表...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 199
精华内容 79
关键字:

数组中唯一只出现一次的数字