1. LC136.只出现一次的数字
题目链接
解法一：
先给数字排序，如果num[i]与nums[i-1]或nums[i+1]都不一致，则返回nums[i]。
class Solution {public int singleNumber(int[] nums) {if (nums.length == 1){return nums[0];}Arrays.sort(nums);for (int i=0; i<nums.length; i++){if (i == 0){if (nums[i+1] != nums[i]){return nums[i];}continue;}if (i == nums.length-1){if (nums[i-1] != nums[i]){return nums[i];}continue;}if (nums[i] != nums[i-1] && nums[i] != nums[i+1]){return nums[i];}}return -1;}
}
解法二：
异或
补充知识点： Java位运算
太强了!!!
int ans = nums[0];
if (nums.length > 1) {for (int i = 1; i < nums.length; i++) {ans = ans ^ nums[i];}}return ans;
所以两个相同的数异或，必然是0；0与任何数异或，必然是任何数。
2. LC169. 多数元素
题目链接
解法一：遍历数组，维护哈希map，key是数值，value是该数值出现的次数，如果value一旦大于n/2，则返回结果。
class Solution {public int majorityElement(int[] nums) {if (nums.length == 1){return nums[0];}Map<Integer, Integer> map = new HashMap<>();for (int i: nums){if (map.containsKey(i)){int count = map.get(i);count++;if (count > nums.length/2){return i;}map.put(i, count);}else{map.put(i, 1);}}return -1;}
}
解法二（技巧）：
因为一定存在多数元素，且多数元素的定义是在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
所以将数组排序后，数组中下标为 ⌊n/2⌋ 的元素（下标从 0 开始）一定是众数。
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}
