【Java 搜索二维矩阵 I II，多数元素 I II，分治法 二分法 摩尔投票法】

题目1：力扣-搜索二维矩阵https://leetcode.cn/problems/search-a-2d-matrix/description/

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

分治-排除法

分治排除法-代码实现

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i = 0;int j = matrix[0].length  - 1;while (i < matrix.length && j >= 0) { //还有剩余元素if (matrix[i][j] == target) {//找到目标值return true;}if (matrix[i][j] < target) {i++; //改行剩余元素全部小于target，排除} else {j--; //改列剩余元素全部大于target，排除}}//若都不满足return false;}
}

二分法

由于矩阵的每一行是递增的，且每行的第一个数大于前一行的最后一个数，如果把矩阵每一行拼在一起，我们可以得到一个递增数组。
例如示例 1，三行拼在一起得

a=[1,3,5,7,10,11,16,20,23,30,34,60]
由于这是一个有序数组，我们可以用二分查找判断 target 是否在 matrix 中。

代码实现时，并不需要真的拼成一个长为 mn 的数组 a，而是将 a[i] 转换成矩阵中的行号和列号。

例如示例：i = 9 对应的 a[i]=30，由于矩阵有 n=4 列，所以 a[i] 在第i / n=2行，在第 i mod n = 1 列。

一般地，有a[i]=matrix[⌊i / n⌋][i mod n]

二分法-代码实现：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int left = -1;int right = m * n;while (left + 1 < right) { //还有剩余元素，左闭右开int mid = (left + right) >>> 1; //取中间值int x = matrix[mid / n][mid % n]; //转化到二维矩阵中if (x == target) {return true;}if (x < target) {left = mid;} else {right = mid;}}//若都不满足return false;}
}

题目2：力扣-搜索二维矩阵IIhttps://leetcode.cn/problems/search-a-2d-matrix/description/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9

解题思路：同题目1中分治法类似，从左上角一行或一列的排除，逐步缩小矩阵的范围，逐步找到目标值target

分治法-代码实现

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i = 0;int j = matrix[0].length - 1;while (i < matrix.length && j >= 0) {if (matrix[i][j] == target) {return true;}if (matrix[i][j] > target) {j--;} else {i++;}}return false;}
}

题目3：力扣-多数元素https://leetcode.cn/problems/majority-element/description/

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：
n == nums.length
1 <= n <= 5 * 104
-10^9 <= nums[i] <= 10^9

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

摩尔投票法

候选人(cand_num)初始化为 nums[0]，票数 count 初始化为 1。
当遇到与 cand_num 相同的数，则票数 count = count + 1，否则票数 count = count - 1。
当票数 count 为 0 时，更换候选人，并将票数 count 重置为 1。
遍历完数组后，cand_num 即为最终答案。

为何这行得通呢？
投票法是遇到相同的则 票数 + 1，遇到不同的则 票数 - 1。
且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。
因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
这就相当于每个 “多数元素” 和其他元素 两两相互抵消，抵消到最后肯定还剩余 至少1个 “多数元素”。

无论数组是 1 2 1 2 1，亦或是 1 2 2 1 1，总能得到正确的候选人。

摩尔投票法-代码实现

class Solution {public int majorityElement(int[] nums) {int candNum = nums[0];int count = 1;for (int it : nums) {if (candNum == it){count++;} else if (--count == 0) {candNum = it;count = 1;}}return candNum;}
}

集合法

• 集合法需另外开辟空间，空间复杂度高，
• 排序后取中间值，时间复杂度高

或者使用Map集合key值表示数组元素，value值表示元素个数，最后遍历Map集合的Entery，寻找 value 值> nums.length / 2 的 key 即可。

class Solution {public int majorityElement(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (int it : nums) {map.put(it, map.getOrDefault(it, 0) + 1);}int len = nums.length >> 1;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() > len) {return entry.getKey();}}return -1;}
}

题目4：力扣-多数元素IIhttps://leetcode.cn/problems/majority-element-ii/description/

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：nums = [3,2,3]
输出：[3]
示例 2：

输入：nums = [1]
输出：[1]
示例 3：

输入：nums = [1,2]
输出：[1,2]

提示：

1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

同第3题，可以使用集合法，秒杀

摩尔投票法

通过上面第3题摩尔投票法的原理，我们可以扩展到寻找出现次数超过 n/3 的众数，这样的众数最多有两个（两个数量相加超过了 2/3，剩余的即使全部一样也不可能超过 1/3），我们声明两个候选者及其对应的两个数量即可，同样地遍历数组，遇到新的数拿它与候选者进行抵消，直到最后遍历完成，两个候选者中存储的就是可能的众数，我们一样要再次遍历数组，统计出这两个候选者的出现的总次数才能确定它们是不是众数。

同样地，我们还可以扩展到寻找出现次数超过 n/k 次的众数，这样的众数最多有 k-1 个。

摩尔投票法-超1/3，两候选代码实现

class Solution {public List<Integer> majorityElement(int[] nums) {// 摩尔投票法List<Integer> ans = new ArrayList<>();// cand是候选者，count是次数int cand1 = 0, count1 = 0;int cand2 = 0, count2 = 0;for (int it : nums) {if (cand1 == it) {// 如果是第一个候选者count1++;} else if (cand2 == it) {// 如果是第二个候选者count2++;} else if (count1 == 0) {// 还没有第一个候选者，或者之前的次数已经归0了cand1 = it;count1 = 1;} else if (count2 == 0) {// 还没有第二个候选者，或者之前的次数已经归0了cand2 = it;count2 = 1;} else {// 当前数与两个候选者都不同count1--;count2--;}}// 再次统计两个候选者的总票数count1 = count2 = 0;for (int num : nums) {if (cand1 == num) {count1++;} else if (cand2 == num) {count2++;}}// 加入结果if (count1 > nums.length / 3) ans.add(cand1);if (count2 > nums.length / 3) ans.add(cand2);return ans;}
}