【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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s