【LeetCode】第43天 - 136. 只出现一次的数字 | 169. 多数元素

文章目录

• ​​136. 只出现一次的数字​​

• ​​题目描述​​
• ​​解题思路​​
• ​​代码实现​​

• ​​169. 多数元素​​

• ​​题目描述​​
• ​​解题思路​​
• ​​代码实现​​

136. 只出现一次的数字

题目描述

解题思路

此题可以运用异或运算的性质，遍历一次数组，将所有元素做一次异或运算，所有元素的异或运算结果即为数组中只出现一次的数字。

异或运算的性质

• 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
• 任何数和其自身做异或运算，结果是 000，即 a⊕a=0。

此题比较简单，但位运算使我们很容易忽略掉的方法，用好位运算有时会大大简化题目和代码。

代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for(int i=0;i<nums.length;i++){
            single ^= nums[i];
        }

        return single;
    }
}

169. 多数元素

题目描述

解题思路

先随机初始化一个数maj，维护它出现的次数count。遍历数组动态改变maj的值，以及它出现的次数。

maj的值，以及count更新规则如下：

• 遍历数组，比较nums[i]与maj是否相等，如果相等，次数count++；
• 如果不等，则判断count是否大于0，如果count>0,则count–；否则，将maj值更新为当前元素值nums[i]。
• 遍历结束，maj即为所求。

代码实现

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;      //计数器
        int maj = 0;        // 当前的众数
        for(int i=0;i<nums.length;i++){
            if(nums[i] == maj){     //与maj相等，计数器+1
                count++;
            }else{                  //不等
                if(count > 0){      // 先判断计数器是否大于0
                    --count;        // 大于0，则计数器-1
                }else{              // 计数器小于0
                    maj = nums[i];  // 将当前值赋予为众数
                }
            }
        }

        return maj;             // 遍历完成maj值，即为多数元素
    }
}