1.数组中出现次数超过一半的数字

1.1 先排序然后取中间的数。

1.2 使用 HashMap 统计出现次数。

public int moreThanHalfNum(int [] array) {if (array == null) {return 0;}Map<Integer, Integer> res = new HashMap<>();int len = array.length;for (int i = 0; i < len; i++) {res.put(array[i], res.getOrDefault(array[i], 0) + 1);if (res.get(array[i]) > len / 2) {return array[i];}}return 0;
}

1.3 使用 result 记录数字，count 记录出现次数，降低空间复杂度。

public int majorityElement(int [] nums) {int count = 0;int result = 0;for (int num : nums) {if (count == 0) {result = num;}count += (num == result) ? 1 : -1;}return result;
}

2.数组中只出现一次的数字

2.1 使用 Set 集合，当出现重复的数时，直接将 key 删除，遍历结束后 set 中只会剩下出现了一次的数字。

2.2 位运算。

class Solution {public int singleNumber(int[] nums) {int single = 0;for(int num: nums){single ^= num;}return single;}
}

使用位运算解答只出现一次的数字的三道题目：只出现一次的数字I，II，III

3.颜色分类问题

3.1 基于冒泡排序的快慢双指针。

public void sortColors(int[] nums) {int n = nums.length;int left = 0;// 把0换到最前边for (int right = 0; right < n; right++) {if (nums[right] == 0) {int temp = nums[right];nums[right] = nums[left];nums[left] = temp;left++;}}// 把1换到2的前边for (int right = left; right < n; right++) {if (nums[right] == 1) {int temp = nums[right];nums[right] = nums[left];nums[left] = temp;left++;}}
}

3.2 将 3.1 的两次循环合并为一次循环，采用三指针。

public void sortColors(int[] nums) {// left表示为0的位置，right表示为2的位置int left = 0, right = nums.length - 1;// index表示为1的位置int index = 0;// right右边都是2，所以index就不需要继续移动了while (index <= right) {if (nums[index] == 0) {swap(nums, index++, left++);} else if (nums[index] == 2) {swap(nums, index, right--);} else {index++;}}
}
public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ♥
算法通关村专栏：不易|算法通关村 ♥