每日一题#1——位运算

寄语

时光流转，愿你终有一天能和你重要的人重逢。
　　　　　　　　 ——艾拉《可塑性记忆》

引言

从今天开始会写blog，主要是记笔记以防后期忘记，同时也会记一些重要的知识点.第一篇文稿测试.

题目描述

给你一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
1
2
3
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

看到这道题，我脑子里第一个想法就是用内置函数count()，它的功能是计算序列中的元素数量。

如果不填参数，将返回元素的个数。若填写参数，这个函数的功能就会变成计算序列中满足某个条件时的元素数量。

方法和思路

方法一：内置函数

public int[] SingleNumber(int[] nums) {
　int[] answer = new int[2];
　int j = 0;
  //遍历数组,找到只出现一次的值
　for (int i = 0; i < nums.Length; i++) {
　　int count = nums.Count(n => n == nums[i]);
　　if(count == 1) {
　　　answer[j] = nums[i];
　　　j++;
　　}
　}
　return answer;
}

消耗时间2748ms 和空间44.10MB

方法二：哈希集合

基于内置函数真的太慢的情况下，我想了一个别的方法。

先创建一个哈希集合，如果在哈希集合中找到了，说明这个数字出现了两次；反之如果没找到，说明这个数字只出现了一次。

public int[] SingleNumber(int[] nums) {
　HashSet<int> numsCounts = new();
　foreach (int i in nums) {
　　//若找到重复元素，则剔除；没找到就添加进去
　　if(numsCounts.Contains(i))
　　　numsCounts.Remove(i);
　　else
　　　numsCounts.Add(i);
　　}
　return numsCounts.ToArray();
}

以下是对代码的优化:

//若添加失败(说明重复)则把这个数字剔除
if(!numsCounts.Add(i))
      numsCounts.Remove(i);

消耗时间152ms 和空间42.55MB

方法三：位运算

因为这个题目的标签里面有位运算，所以我一直在想怎么用，但是一整天都没想出来。

怎么办呢？那只好去翻翻题解了。现在似乎有点明白了.

X⊕X=0(异或时,相同数字会抵消) 　　　　　
0⊕X=X(异或时,任何数和0发生关系都等于那个数)

异或运算的原理如上所示，现在将所有数字异或，将得到一个不为0的数。

若输入为[1, 2, 1, 3, 2, 5]，那他们的异或结果就是3^5,是一个不知道的数.

然后将这个得出来的数的补码(一种负数二进制形式)和它自己(也就是刚刚异或的结果)进行与运算。

这样可以得到只有最低位是1的二进制码，这个位就是两个只出现一次的数字在二进制表示上的差异。

以下为步骤表格：看表格，3和5从右往左第一个差异是不是第二位不一样？所以异或结果的补码只有第二位为1。

步骤/数字 3 5 3^5
二进制码 011 101 110
反码 100 010 001
补码 101 011 010

步骤/数字	3	5	3^5
二进制码	011	101	110
反码	100	010	001
补码	101	011	010

现在就可以对原数组的每一个数进行与运算后分类，有0的分为一组，有1的分为一组。

以下是分类结果：针对输入为 [1, 2, 1, 3, 2, 5]的为例

1：2, 2, 3
0：1, 1, 5

经过”分治”的过程，问题转化成了简单的 **”在偶数次数字里找到只出现一次的元素”**。

现在只要遵循异或的运算规则，将一个类总的所有元素全部异或，偶数次的元素会被相互抵消，然后就会剩下只出现一次的元素了。

public int[] SingleNumber(int[] nums) {
　//定义
　int numsxor = 0;
　int[] res = new int[2];
　//所有元素异或
　foreach (int num in nums)
　　numsxor ^= num;
　//异或结果和补码与运算，得到最低位为1的二进制码
　//就是取最右边的那个1，这个1保留，其他全改成0
　int answer = numsxor & (-numsxor);
　//用这个码对数组分类
　foreach (int num in nums)
　{
　　//全部异或抵消得到结果
　　if ((answer & num) == 0)
　　　res[0] ^= num;
　　else
　　　res[1] ^= num;
　}
　return res;
}

通过这种方法得出的结果，耗时 (132ms) 和空间 **(42.39MB)**。

结语和留言

今天是第一天，希望自己能坚持下去。

笔记完毕编辑完毕时间CST 10.16 23:55

最后修改于8.15 00:05

蝠池茶园