LeetCode—数组中数字出现的次数
2021-06-06 09:04
标签：信息 要求 问题： span 循环 leetcode 重要 one 程序 今天刷力扣遇到了这样的问题： 一个整型数组 之前没有遇到过类似的题型，看到之后很懵，看了题解才知道要用到分组异或的方式进行分组。题解又看了十分钟才终于理解解法的含义。。。 先描述一下题解的思路： 首先认识到异或"^"的本质是相同位为0，不同位为1。同时，异或满足交换律和结合律 如果有一个数组【2， 1， 3， 3， 2， 5】，如果要想进行异或运算，其结果是与【1， 2， 2， 3， 3， 5】相同的。 通过前面的结论，数组中的两个2和两个3是可以消除掉的，整个数组的运算就相当于“1 ^ 5”，0001与0101进行异或，结果为0100。 这个结果相当重要，我们可以从中提取出两条关键信息 我们可以利用这个不相同的位来对原有的数组进行分组，分组方式是将数组中每个元素判断一次倒数第三位是0还是1，如果为0，那么就将它放入A组，如果为1，我就将它放入B组。这样，数组中的两个不同数字一定会被分在不同的组。 那么这样的话数组中的6个元素就井然有序的分为了两组，他们每一组的倒数第三位都是统一的0或1。由于数组中有重复的数字，而且重复的数字二进制数一定是相同的，因此相同的数字一定被分在了同一组，我们对两组分别进行异或运算，由前面的结论可以知道相同的数字可以消除，那么最后两组中只能分别剩下一个元素，因为他们没有“伙伴”可以一起消除掉。 最后输出这两个数，就得到了最终的答案。 下面附代码 LeetCode—数组中数字出现的次数 标签：信息 要求 问题： span 循环 leetcode 重要 one 程序 原文地址：https://www.cnblogs.com/carl-66/p/14613063.htmlnums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
1 public int[] singleNumbers(int[] nums) {
2 int k = 0; //k为数组中所有元素求异或运算的结果
3 for (int num : nums) {
4 k ^= num;
5 }
6 int mask = 1; //mask为两不同数字二进制数中不同的那一位，这里默认取1（0001，1的位置会在后面while循环中进行调整），如果条件允许也可以指定其他位，在这里为了运算方便指定为从右向左的第一位
7 while ((k & mask) == 0) {
8 mask ;
9 }
10 int a = 0;
11 int b = 0;
12
13 for (int num : nums) {
14 if ((num & mask) == 0) { //遍历数组，按照mask位的数字分组
15 a ^= num; //为0，分在a组
16 } else {
17 b ^= num; //为1，分在b组
18 }
19 }
20 return new int[]{a, b};
21 }
上一篇：C++之继承和派生
下一篇：Java 安装开发环境