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

x33g5p2x  于2022-03-09 转载在 其他  
字(0.8k)|赞(0)|评价(0)|浏览(135)

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值,即为多数元素
    }
}

相关文章