精华内容
下载资源
问答
  • 题目描述 在一个数组中除了一个数字只出现一次之外,其他数字出现了三次。请找出那个只出现一次数字。 这题有点意思,其他数字都重复了三次,一般位运算就消不掉... * 数组中唯一出现一次数字, * 除此之...

    题目描述

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

    这题有点意思,其他数字都重复了三次,一般位运算就消不掉了。

    解题思路

    • 将所有数字的二进制表示的对应位都加起来,如果某一位能被三整除,那么只出现一次的数字在该位为0;反之,为1。
    算法图解

    在这里插入图片描述

    参考代码:
    package offer;
    
    /**
     * 数组中唯一个出现一次的数字,
     * 除此之外其他数字都出现了三次
     */
    public class Offer56_2 {
        public static void main(String[] args) {
            int nums[] = {2, 4, 3, 2, 3, 2, 3};
            System.out.println(findAppearOnce(nums));
        }
    
        private static int findAppearOnce(int[] arr) {
            if (arr == null || arr.length < 4) {
                return 0;
            }
            int[] bitSum = new int[32];
            // 求每一位的和
            for (int i = 0; i < arr.length; i++) {
                int bitMask = 1;
                for (int j = 31; j >= 0; j--) {
                    int bit = arr[i] & bitMask;  //注意arr[i]&bitMask不一定等于1或者0,有可能等于00010000
                    if (bit != 0)
                        bitSum[j] += 1;
                    bitMask = bitMask << 1;
                }
            }
    
            int result = 0;
            for (int i = 0; i < 32; i++) {
    
                result = result << 1;
                result += (bitSum[i] % 3);
    
            }
            return result;
    
        }
    }
    
    
    

    附录

    该题源码在我的 ?Github 上面!

    展开全文
  • 在一个数组中除一个数字只出现一次之外,其他数字出现了三次。请找出那个只出现一次数字。 思路:我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除,那么那个只出现一次数字二...

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

    思路:我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1。

    代码如下:

    int FindNumberAppearingOnce(int numbers[],int length)

    {

     if(numbers==nullptr||length<=0)

    {

     throw new std::exception("Invalid input.");

    }

    int bitSum[32]={0};

    for(int i=0;i<length;++i)

    {

     int bitMask=1;

    for(int j=31;j>=0;--j)

    {

     int bit=numbers[i]&bitMask;

    if(bit!=0)

     bitSum[j]+=1;

      bitMask=bitMask<<1;

    }

    }

    int result=0;

    for(int i=0;i<32;++i)

    {

     result=result<<1;

    result+=bitSum[i]%3;

    }

    return result;

    }

    这种解法的时间效率是O(n)。我们需要一个长度为32的辅助数组存储二进制表示的每一位的和。由于数组的长度是固定的,因此空间效率是O(1)。该解法比其他两种直观的解法效率都高:(1)我们很容易就能从排序的数组中找到只出现一次的数字,但排序需要O(nlogn)时间;(2)我们也可以用一个哈希表来记录数组中每个数字出现的次数,但这个哈希表需要O(n)的空间。

    展开全文
  • 题目描述 一个整型数组里除了两个数字之外,其他的数字出现了两次。请写程序找出这两个只出现一次数字。 思路: 1. 从头到尾依次异或数组中的...这样每个子数组包含一个只出现一次数字,而其他数字都成对...

    题目描述

    一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

     

    思路:

    1. 从头到尾依次异或数组中的每个数字,找到结果数字中第一个为1的位置,记为第n位。

    2.以第n位是不是1为标准把原数组中的数字分成两个数组,第一个子数组中每个数字的第n位都是1,第二个子数组中每个数字的第n位都是0。这样每个子数组包含一个只出现一次的数字,而其他数字都成对出现两次。

    3. 在每个子数组中,从头到尾依次异或数组中的数字,最终的结果就是子数组中只出现一次的数字。

    # -*- coding:utf-8 -*-
    class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            if not array:
                return None
            resultExclusiveOR = 0
            for i in range(len(array)):
                resultExclusiveOR ^=array[i]
            indexOf1 = self.FindFirstBitIs1(resultExclusiveOR)
            num1 = num2 = 0
            for i in range(len(array)):
                if self.IsBit1(array[i], indexOf1):
                    num1 ^= array[i]
                else:
                    num2 ^= array[i]
            return [num1, num2]
        #找到最右边是1的位
        def FindFirstBitIs1(self, num):
            indexBit = 0
            while num&1 == 0:
                num = num>>1
                indexBit+=1
            return indexBit
        #判断num从右到左第IndexOf1位是不是1
        def IsBit1(self, num, indexOf1):
            num = num>>indexOf1
            return (num&1)
        

    题目描述:

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

     

    思路:

    如果一个数字出现了三次,那么它的二进制的每一位也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。由于python中的二进制保存的不是补码,所以正负数要分开讨论。这个方法比较慢。

    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return None
        
            nums_p = []
            nums_n = []
            for i in range(len(nums)):
                if nums[i]>=0:
                    nums_p.append(nums[i])
                else:
                    nums_n.append(-nums[i])
            
            bitSum_p = [0]*32
            for i in range(len(nums_p)):
                bitMask = 1
                for j in range(31, -1, -1):
                    bit = nums_p[i] & bitMask
                    if bit!=0:
                        bitSum_p[j]+=1
                    bitMask = bitMask<<1
            result_p = 0
            for i in range(32):
                result_p = result_p<<1
                result_p+=bitSum_p[i]%3
            
            bitSum_n = [0]*32
            for i in range(len(nums_n)):
                bitMask = 1
                for j in range(31, -1, -1):
                    bit = nums_n[i] & bitMask
                    if bit!=0:
                        bitSum_n[j]+=1
                    bitMask = bitMask<<1
            result_n = 0
            for i in range(32):
                result_n = result_n<<1
                result_n+=bitSum_n[i]%3
            result_n = -result_n
            
            return(result_n+result_p)

    思路二:利用python中的set

    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
            return (3*sum(set(nums))-sum(nums))//2

     

    展开全文
  • 题目:在一个数组中除一个数字只出现一次之外,其他数字出现了三次。请找出那个只出现一次数字。 解题思路: 如果一个数字出现三次,那么这个数表示的二进制的每一位的和都能被3整除。把不能整除的数加起来...

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

    解题思路:

    如果一个数字出现三次,那么这个数表示的二进制的每一位的和都能被3整除。把不能整除的数加起来就是那个只出现一次的数字。

    如:在数组{8,6,7,8,8,6,6}中,3个8的二进制的每一位的和为:1000+ 1000+ 1000 = 3000,3个6的二进制的每一位的和为:0110 + 0110 + 0110 = 0330,7的二进制为0111,那么整个数组的二进制的和为:3441。用它除以(%)3余0111,即为7。

    程序为:

    #include<stdio.h>
    #include<stdlib.h>
    
    int FindOnlyOneNum(int arr[], int len)
    {
    	//处理异常情况
    	if (arr == NULL || len <= 0)
    	{
    		return -1;
    	}
    	//定义一个数组存放数组各元素各位上的值的和
    	int bitarr[32] = { 0 };
    	//遍历整个数组,计算数组各元素在各位上的和
    	for (int i = 0; i < len; i++)
    	{
    		int bitmask = 1;//位掩码
    		for (int j = 31; j >= 0; j--)
    		{
    			int bit = arr[i] & bitmask;
    			if (bit != 0)
    			{
    				bitarr[j] += 1;
    			}
    			bitmask = bitmask << 1;
    		}
    	}
    	//用数组各元素各位上的和除以3,记录不被3整除的数
    	int result = 0;
    	for (int k = 0; k < 32; k++)
    	{
    		result = result << 1;
    		result += bitarr[k] % 3;
    	}
    	return result;
    }
    
    int main()
    {
    	int arr[] = { 8, 6, 7, 8, 8, 6, 6 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	printf("数组的元素为:");
    	for (int i = 0; i < len; i++)
    	{
    		printf("% d", arr[i]);
    	}
    	printf("\n");
    	int ret = FindOnlyOneNum(arr, len);
    	printf("数组中只出现一次的元素是:% d\n", ret);
    	system("pause");
    	return 0;
    }

    运行的结果为:

     

    展开全文
  • 题目描述: 一个整型数组里出来两个数字之外,其他的数字出现了两次。...再来考虑一种简单一点的情况:一个数组中只有一个元素出现唯一一次,而有其他元素都出现2次。 那么我们用0依次异或数组中每一个元素,得到
  • 剑指offer[c++] 数组中只出现一次数字题目:一个整型数组里除了两个数字之外,其他的数字出现了两次。请写程序找出这两个只出现一次数字。思路:借鉴了...
  • 数组中只出现一次数字(python解法)

    千次阅读 2019-06-16 17:55:57
    数组中只出现一次数字题目解法解法一 题目 题目链接:数组中只出现一次数字 解法 解法一 题目特点为,列表只有两种元素,一种为出现次数是两次的,一种为出现次数是1次的。因此,可以利用下面的方法来推断出...
  • * 2、数组中所有的数字做异或操作,最后的结果就是出现一次唯一数字 2、一个整型数组里除了两个数字之外,其他的数字出现了两次。找出这两个数字 思路: * 1、两个相同的数字做异或操作,结果是0 * 2...
  • 上篇博文我们求的是两个只出现一次数字,且时间复杂度为O(n),这次是三个,可以同样考虑将数组先分成两个子数组,求出其中一个只出现一次数字,而后再将另一个子数组分成两个子数组,再分别求这两个只出现一...
  • 思路:上篇博文已经了解到异或去重的原理,而且知道如果只有一个只出现一次数字的求法,但这里是有两个只出现一次数字,我们便要想办法把他分为两个子数组,每个子数组中包含一个只出现一次数字,其他的数字...
  • 根据异或去重的原理,我们知道如果只有一个只出现一次数字的求法,但这里是有两个只出现一次数字,我们便要想办法把他分为两个子数组,每个子数组中包含一个只出现一次数字,其他的数字出现了两次。...
  • 题目:数组中唯一只出现一次数字 在一个数组中除了一个数字只出现一次之外,其他数字出现了三次。请找出那个只出现一次数字。 主要思路:基于位运算,若一个数字出现三次,那么它的二进制表示的每一位也...
  • 题目描述 ... 当数组中只有两个数出现一次,其余数都出现偶数次,那么数组中所有数字异或的结果相当于这两个数字异或的结果 两个数异或的结果中为1的位,说明这两个数在这个位不同 根据在这个位是...
  • 题目一:一个数组里除了一个数之外,其他的数都...也就是说,如果我们从头到尾异或数组中的每一个数字,那么结果为只出现一次数字,因为出现两次的数字全部抵消了。 void FindNumberAppearOnce(int data[] ,int
  • /*找出一个数组中的两个唯一出现一次数字,其他数组出现了两次。 思路:还是和当时的那道题目一样,用HashMap记录每个数字出现的次数,返回唯一两个get为0的数,加个flag分开即可*/ public class item38 { ...
  • 题目:一个整型数组里除了一个数字之外,其它的数字出现了两次。请写程序找出这个只出现一次的...如果我们从头到尾依次异或数组中的每一个数,那么最终的结果就是那个只出现一次数字,因为其他出现两次的数字...
  • 请写程序找出这两个只出现一次数字。 算法:位运算 数据结构:数字 编程语言:C++ class Solution { public: void FindNumsAppearOnce(vector&lt;int&gt; data,int* num1,int *num2) { i...
  •  一个数组中,存在两个只出现一次数字,其余的数字出现两次。要求在时间复杂度o(n),空间复杂度为o(1)的情况下找出这两个数字。   二 问题分析  此题实际考察了,对位操作的理解。首先进行简化,考虑只有...
  • 思路:利用异或的特点,一个数的二进制异或自己,结果为0,既然数组中只有两个数字出现一次,其他出现两次,那么首先考虑这样一个问题:一个数组中,只有一个数字出现一次,其他数字出现两次,那么需要全部异或,...
  • 一个整型数组里除了两个数字...请写程序找出这两个只出现一次数字。 C++ class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { map<int,int> tmp; ...
  • 找出数组只出现一次数字,是一系列的笔试题,来考察大家对位运算的掌握,下面我们从最简单的开始来看看吧! 一、题目:一个整型数组里只有一个数字出现一次,其余数字出现了两次,请写程序找出出现一次的...
  • 题目:一个整型数组里除了两个数字之外,其他的数字出现了...也就是说, 如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次数字,因为那些成对出现两次的数字全部在异或抵消了。
  • 找出数组中只出现一次数字题目题目分析方法1方法2 题目 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个 元素均出现两次。找出那个只出现一次的元素。 示例 示例1:输入:[2,2,1] 输出:...
  • 请写程序找出这个只出现一次数字。要求时间复杂度是O(n),空间复杂度是O(1)。 分析:由于题目要求时间复杂度为O(n),所以先排序然后比较相邻数字是否相同的思路被排除。  空间复杂度是O(1),辅助空间被限制...
  • 1.数组中有一个数字只出现一次数组中有很多成对出现数字,这些数字的顺序是随机出现的。但是里面有一个数字缺失,怎样用最快的方式将这一个数字找出来?由于只有一个数字出现一次,其他都是成对出现的,所以此时...
  • 找出数组中唯一出现奇数的数

    千次阅读 2018-12-22 11:34:48
    已知数组长度为n,且其中只有数字出现过奇数,其他数字出现偶数,找出出现奇数的这个数。 思路 遍历数组,依次异或。 代码实现 public int solution (int[] nums) { int res = 0; for (int value: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 117,511
精华内容 47,004
关键字:

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