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

2024-08-24 01:04

本文主要是介绍【Java 搜索二维矩阵 I II,多数元素 I II,分治法 二分法 摩尔投票法】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

搜索二维矩阵 I II,多数元素,分治法 & 二分法 & 摩尔投票法

  • 题目1:力扣-搜索二维矩阵[https://leetcode.cn/problems/search-a-2d-matrix/description/](https://leetcode.cn/problems/search-a-2d-matrix/description/)
    • 分治-排除法
      • 分治排除法-代码实现
    • 二分法
      • 二分法-代码实现:
  • 题目2:力扣-搜索二维矩阵II[https://leetcode.cn/problems/search-a-2d-matrix/description/](https://leetcode.cn/problems/search-a-2d-matrix/description/)
      • 分治法-代码实现
      • 题目3:力扣-多数元素[https://leetcode.cn/problems/majority-element/description/](https://leetcode.cn/problems/majority-element/description/)
    • 摩尔投票法
      • 摩尔投票法-代码实现
    • 集合法
  • 题目4:力扣-多数元素II[https://leetcode.cn/problems/majority-element-ii/description/](https://leetcode.cn/problems/majority-element-ii/description/)
    • 摩尔投票法
      • 摩尔投票法-超1/3,两候选代码实现

题目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;}
}

这篇关于【Java 搜索二维矩阵 I II,多数元素 I II,分治法 二分法 摩尔投票法】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101003

相关文章

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

springboot项目如何开启https服务

《springboot项目如何开启https服务》:本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序