算法通过村第三关-数组黄金笔记|数组难解

文章目录

  • 前言
    • 数组中出现超过一半的数字
    • 数组中只出现一次的数字
    • 颜色的分类问题(荷兰国旗问题)
      • 基于冒泡排序的双指针(快慢指针)
      • 基于快排的双指针(对撞指针)
  • 总结


前言


提示:苦不来自外在环境中的人、事、物,只是自内的妄想和执着。 --金惟纯

这里整理一些比较经典的题目,巩固一下数组的学习。

数组中出现超过一半的数字

题目介绍参考:剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣(LeetCode)
在这里插入图片描述
对于这种题目,如果没有思路的话,我们可以先把常见的数据结构和算法策略过一般,这里参考以前的文章巩固一下。算法通关村第一关-链表白银挑战笔记|公共子节点_师晓峰的博客-CSDN博客
在这里插入图片描述
我们想一下,查找统计出所有出现的个数,大于一半就可以,这不就是一种想法🥰,排序行不行呢,对数组进行排序,超过一半必定是中位数。

如果不了解中位数这个概念的:
🐟聪明回答:

在数学中,中位数指的是一组数字排序后的中间值,即将一组数字从小到大排列,中间的那个数就是中位数。如果一组数字有奇数个,那么中位数就是排序后的中间数;如果一组数字有偶数个,那么中位数是中间两个数的平均值。中位数可以用来表示一组数据的中心趋势,较为稳定而不易受极端值的影响。

但是如果你不放心的话可以在遍历一遍数组,确定这个数组是否超过一半,所以第二种方法就出来了。这种方法的时间复杂度取决于排序算法的时间复杂度,最快的话O(nlogn),排序的代价比较高,我们试想一下还有别的方法吗💡

我们使用Hash行不行呢?我们先创建一个HashMap的key是元素的值,value是已经出现的次数,然后遍历数组来统计所有元素出现的次数,最后在遍历一边Hash,找到次数超过一半的数字,这不又一种方法出来了。

我们展示一下代码:

	/**
     * 方法1 基于Hash
     * @param array
     * @return
     */
    public static int moreThanHalfNum(int[] array) {
        // 参数校验
        if (array == null || array.length == 0) {
            return 0;
        }
        HashMap<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;
    }

当然采用Hash的方法可以解决,但是这里最多给70,着并不是最优的结果,那么有没有巧妙的方法呢?

拓展:采用上面你的算法时间复杂度为O(n),但是这是用空间复杂度O(n)换来的,那么有没有空间复杂度为O(1)且时间负责度为O(n)的呢?💡

你听说过摩尔投票法则吗?它用来解决多数问题(中位数)可以说是一把利刃。

🐟聪明的回答:

摩尔投票法(Moore’s Voting Algorithm)是一种用于在数组或列表中查找出现次数超过一半的元素的算法。该算法基于以下观察:如果一个元素出现次数超过一半,那么它在数列中出现的次数一定比其他所有元素出现次数之和还要多。

算法步骤如下:

  1. 初始化两个变量:候选元素(candidate)和计数器(count),候选元素用于保存当前被选中的元素,计数器用于统计候选元素的出现次数。
  2. 遍历整个数组或列表,对于每一个元素:
    • 如果计数器为0,将当前元素设为候选元素,将计数器设为1。
    • 否则,如果当前元素与候选元素相同,计数器加1;否则,计数器减1。
  3. 完成遍历后,最后留下的候选元素就是候选元素,但这并不代表它一定是超过一半的元素,只是候选元素的可能性更高。
  4. 最后,再次遍历整个数组或列表,统计候选元素的出现次数。如果它的出现次数确实超过一半,那么它就是超过一半的元素;否则,不存在超过一半的元素。

下面给出一个例子来解释摩尔投票法:
假设我们有一个数组:[2, 4, 5, 2, 2]。

  • 遍历第一个元素2,将其设为候选元素,计数器为1。
  • 遍历第二个元素4,与候选元素不同,计数器减1。
  • 遍历第三个元素5,与候选元素不同,计数器减1。
  • 遍历第四个元素2,与候选元素相同,计数器加1。
  • 遍历第五个元素2,与候选元素相同,计数器加1。
    此时,计数器为2,最后剩下的候选元素是2。
    再次遍历整个数组,统计元素2的出现次数,发现它出现了3次,大于数组长度的一半,所以2就是超过一半的元素。
	/**
     * 方法二:比较特殊的计数法
     *
     * @param array
     * @return
     */
    public static int moreThanHalfNum2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int count = 0;
        Integer candidate = null;
        for (int num : array) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        // check 记得在检查一边
        count = 0;
        int len = array.length;
        for (int num : array) {
            if (num == candidate) {
                count++;
            }
            if (count >= len / 2) {
                return candidate;
            }
        }
        return candidate;
    }

Q&A

Q : 这里问什么要在检查一边,可以不检查?会出现什么问题?

A :必须再检查一边,这里是确保candidate一定是超出一半的数,不检查投出的结果不一定正确[1,2,3],有结果,但是不符合要求。

数组中只出现一次的数字

参考题目介绍:136. 只出现一次的数字 - 力扣(LeetCode)
在这里插入图片描述
在这里插入图片描述
这个题用Set集合解决比较好,Set集合不存储重复元素,这个是该集合的特性。题目说明其他元素都是出现两次,我们刚好可以利用这个操作,当要添加元素的key与集合中已存在的数出现重复的时候,我们就不进行操作,并且将这个key一起删掉,确保只存在一个数,这样遍历一边就可以知道答案了。【注意:确保集合有元素 】

	/**
     * 基于集合寻找
     *
     * @param arr
     * @return
     */
    public static Integer findOneNum(int[] arr) {
        // 校验参数
        if (arr == null || arr.length == 0){
            return null;
        }
        // 特殊处理
        if (arr.length == 1) {
            return arr[0];
        }
        HashSet<Integer> res = new HashSet<>();
        for(int i = 0; i < arr.length; i++){
            if (!res.add(arr[i])){
                res.remove(arr[i]);
            }
        }
        // check 确保set集合存在元素
        if (res.size() == 0){
            return null;
        }
        return (Integer) res.toArray()[0];
    }

当然这个方法也不是最优解,算法就是这么奇妙,有时后令人讨厌,有时候让你欣喜。提示一下,可以想一想位运算来解决:你知道异或这个操作吗?

🐟聪明回答:

计算机中的异或操作(XOR),也称为“排他性或”操作,是一种逻辑运算,用于比较两个值的不同之处。异或操作有以下几条规则:

  1. 同一个值与自身进行异或操作结果为0:A ⊕ A = 0
  2. 任意值与0进行异或操作结果不变:A ⊕ 0 = A
  3. 异或操作满足交换律:A ⊕ B = B ⊕ A
  4. 异或操作满足结合律:(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
  5. 异或操作满足自反性:A ⊕ B ⊕ A = B

举例来说明:

  1. 与自身进行异或操作:7 ⊕ 7 = 0
  2. 与0进行异或操作:5 ⊕ 0 = 5
  3. 交换律:3 ⊕ 5 = 5 ⊕ 3
  4. 结合律:(2 ⊕ 4) ⊕ 6 = 2 ⊕ (4 ⊕ 6)
  5. 自反性:2 ⊕ 4 ⊕ 2 = 4

异或操作在计算机中有很多应用,其中一个常见的应用是用于交换两个变量的值。例如,假设有两个变量a和b,我们可以使用异或操作进行交换如下:

a = a ⊕ b;
b = a ⊕ b;
a = a ⊕ b;

在经过以上操作后,a和b的值就被交换了。

看到了吗?我们可以根据这个自反性质得到我们想要的答案,是不是非常简单😁。

遍历一边就能拿到想要的结果,代码展示:

	/**
     * 基于位运算
     * 0 ^ * = *
     * A ^ B ^ A = B
     * @param arr
     * @return
     */
    public static int findOneNum2(int[] arr) {
        int res = 0;
        for(int num : arr){
            res ^= num;
        }
        return res;
    }

颜色的分类问题(荷兰国旗问题)

参考题目介绍:75. 颜色分类 - 力扣(LeetCode)
在这里插入图片描述
在这里插入图片描述
那我们就来认识一下荷兰的国旗吧:
在这里插入图片描述
感兴趣的可以看看历史:荷兰和俄罗斯的国旗为什么高度相似?到底是谁抄袭谁? (baidu.com)

这个问题很典型,双指针问题,当然可以采用多种方式的双指针解决,我们研究第一种与冒泡类似的,第二种与快排类似。

基于冒泡排序的双指针(快慢指针)

冒泡排序我们都知道,就是根据大小逐步和后面的比较,慢慢调整到整体有序的状态,这种方法是比较稳定的排序方法。

当然我们可以这样考虑:

  1. 第一次遍历,我们将数组中所有0交换到数组的头部
  2. 第二次遍历,只需要处理1和2。

漂亮的双指针代码如下:

 public static void sortColors(int[] nums) {
        // 定义快慢指针
        int n = nums.length;
        int left = 0;
        // 先处理 0 把0移到最左边
        for(int right = 0; right < n; right++) {
            if (nums[right] == 0){
                swap(nums,left,right);
                left++;
            }

        }
        // 接着处理1 把1移到次走遍
        for(int right = left; right < n; right++){
            if (nums[right] == 1){
                swap(nums,left,right);
                left++;
            }
        }

    }
	
	// 采用位运算的方式交换
    public static void swap(int[] nums, int left, int right) {
        nums[left] = nums[left] ^ nums[right];
        nums[right] = nums[left] ^ nums[right];
        nums[left] = nums[left] ^ nums[right];
    }

这里解决的话效果还是可以的,但是如果再进一步问你,可以一次遍历就解决吗?你就要考虑第二种方法了。

基于快排的双指针(对撞指针)

如果要求一次遍历就解决问题,我们要怎么想办法呢?隐约觉得需要使用三个指针才可以:

  • left指针,表示left左侧的元素都是0
  • right指针,便是right右侧的元素都是2
  • index指针,从头到尾遍历数组,根据nums[index]是0还是2决定与left交换还是和right交换

index的位置上的元素代表我们将要处理的数字。index为1,我们不需要做什么,直接+ 1,如果是0,放在左边,如果是2,放在右边,当index == right的时候就可以停止了。

我们画图表示一下:
在这里插入图片描述
这里面的重点在于index的位置为2的时候进行交换后为right–,index不做处理,当然这里考虑到了,index 为 1的情况,所以先不动,1 比较特殊,跳过去就没法处理了。

那么问题来了,index 为0的时候执行交换的话index++,如果存在都会被交换到右边,这里只需要处理1和0的问题就可以了。

代码如下:

 	 /**
     * 采用位运算的方式交换
     * @param nums
     * @param left
     * @param right
     */
    public static void swap(int[] nums, int left, int right) {
        nums[left] = nums[left] ^ nums[right];
        nums[right] = nums[left] ^ nums[right];
        nums[left] = nums[left] ^ nums[right];
    }

    public static void sortColors(int[] nums) {
        // 定义快慢指针
        int left = 0 , index = 0,right = nums.length - 1;
        while(index <= right) {
            if (nums[index] == 2){
                swap(nums,index,right--);
            }else if (nums[index] == 0){
                swap(nums,index++,left++);
            }else {
                index++;
            }
        }
    }

总结

注意:双指针问题,边界和条件。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/91148.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

yolov8热力图可视化

安装pytorch_grad_cam pip install grad-cam自动化生成不同层的bash脚本 # 循环10次&#xff0c;将i的值从0到9 for i in $(seq 0 13) doecho "Running iteration $i";python yolov8_heatmap.py $i; done热力图生成python代码 import warnings warnings.filterwarn…

使用秘籍|如何实现图数据库 NebulaGraph 的高效建模、快速导入、性能优化

本文整理自 NebulaGraph PD 方扬在「NebulaGraph x KubeBlocks」meetup 上的演讲&#xff0c;主要包括以下内容&#xff1a; NebulaGraph 3.x 发展历程NebulaGraph 最佳实践 建模篇导入篇查询篇 NebulaGraph 3.x 的发展历程 NebulaGraph 自 2019 年 5 月开源发布第一个 alp…

【Spring MVC】

目录 &#x1f36e;1 什么是 MVC &#xff1f; &#x1f381;2 Spring MVC 的连接 &#x1f358;2.1 RequestMapping 实现 POST 和 GET 请求 &#x1f963;2.2 GetMapping 只支持 GET 请求 &#x1fad6;2.3 PostMapping 只支持 POST 请求 &#x1f36c;3 Spring MVC 获取参数的…

创建本地镜像

通过前面文章的阅读&#xff0c;读者已经了解到所谓的容器实际上是在父镜像的基础上创建了一个可读写的文件层级&#xff0c;所有的修改操作都在这个文件层级上进行&#xff0c;而父镜像并未受影响&#xff0c;如果读者需要根据这种修改创建一个新的本地镜像&#xff0c;有两种…

Smartbi电子表格软件版本更新,首次推出Excel轻应用和语音播放

Smartbi电子表格软件又又又更新啦&#xff01; 此次更新&#xff0c;首次推出了新特性——Excel轻应用和语音播报。另外&#xff0c;还对产品功能、Demo示例、配套文档进行了完善和迭代。 低代码开发Excel轻应用 可实现迅速发布web应用 业务用户的需求往往都处于“解决问题”…

APP调用bindService的跨进程调用过程

app执行bindService时会经过如下8次跨系统进程调用过程&#xff1a; 第1步&#xff1a;通过AMS.getService跨进程调用 第2步&#xff1a;AMS返回它的IBinder 第3步&#xff1a;通过AMS的IBinder调用AMS的bindService方法 第4步&#xff1a;而AMS存放有Server端的IBinder&…

ChatGPT在医疗系统的应用探索动态

注意&#xff1a;本信息仅供参考&#xff0c;发布该内容旨在传递更多信息的目的&#xff0c;并不意味着赞同其观点或证实其说法。 生成式人工智能&#xff0c;如OpenAI开发的ChatGPT&#xff0c;被认为是可以颠覆医疗行业的工具。尽管该技术刚刚起步&#xff0c;但已有许多医…

Vue2向Vue3过度Vuex核心概念mutations

目录 1 核心概念-mutations1.定义mutations2.格式说明3.组件中提交 mutations4.练习5.总结 2 带参数的 mutations1.目标&#xff1a;2.语法2.1 提供mutation函数&#xff08;带参数&#xff09;2.2 提交mutation 3 练习-mutations的减法功能1.步骤2.代码实现 4 练习-Vuex中的值…

kettle实现爬虫

步骤概览 获取请求 请求地址 东方财富网股票请求 自定义常量数据 获取HTTP请求之前&#xff0c;必须先定义一个URL常量作为HTTP client的输入 HTTP client 注&#xff1a;此处得到的数据并不是原生的json字符串&#xff0c;自己可以用文本文件输出测试以下。如下图 JavaScri…

Vue2向Vue3过度核心技术路由

目录 1 路由介绍1.思考2.路由的介绍3.总结 2 路由的基本使用1.目标2.作用3.说明4.官网5.VueRouter的使用&#xff08;52&#xff09;6.代码示例7.两个核心步骤8.总结 3 组件的存放目录问题1.组件分类2.存放目录3.总结 4 路由的封装抽离5 Vue路由-重定向1.问题2.解决方案3.语法4…

谈谈子网划分的定义、作用、划分方式以及案例

个人主页&#xff1a;insist--个人主页​​​​​​ 本文专栏&#xff1a;网络基础——带你走进网络世界 本专栏会持续更新网络基础知识&#xff0c;希望大家多多支持&#xff0c;让我们一起探索这个神奇而广阔的网络世界。 目录 一、子网划分的定义 二、子网掩码的作用 1、…

林业气象站——林业种植气象观测

林业气象站是一种用于观测林区气象环境的仪器&#xff0c;能够观测林区天气、土壤等自然环境参数&#xff08;温度、湿度、风速、风向、降雨量、气压、放射线、土壤湿度等&#xff09;&#xff0c;为开展环境观测、天气预报、灾害预警、林区虫害防治起到综合指导作用。 林业气…

Unity中的数学基础——贝塞尔曲线

一&#xff1a;前言 一条贝塞尔曲线是由一组定义的控制点P0到 Pn&#xff0c;n1为线性&#xff0c;n2为二次......第一个和最后一个控制点称为起点和终点&#xff0c;中间的控制点一般不会位于曲线上 获取两个点之间的点就是通过线性插值&#xff08; Mathf.Lerp&#xff09…

基于Python+djangoAI 农作物病虫害预警系统智能识别系统设计与实现(源码&教程)

1.背景 随着科技的发展&#xff0c;机器学习技术在各个领域中的应用越来越广泛。在农业领域&#xff0c;机器学习技术的应用有助于提高农作物的产量和质量&#xff0c;降低农业生产的成本。本文针对农作物健康识别问题&#xff0c;提出一种基于机器学习方法的农作健康识别系统&…

FOC之SVPWM学习笔记

一、参考资料 【自制FOC驱动器】深入浅出讲解FOC算法与SVPWM技术 - 知乎FOC入门教程_zheng是在下的博客-CSDN博客DengFOC官方文档技术干货 |【自制】FOC驱动板SVPWM_扇区判断_时间计算_哔哩哔哩_bilibili 二、FOC控制算法流程框图 在FOC控制中主要用到三个PID环&#xff0c;从内…

picGo+gitee+typora设置图床

picGogiteetypora设置图床 picGogitee设置图床下载picGo软件安装picGo软件gitee操作在gitee中创建仓库在gitee中配置私人令牌 配置picGo在插件设置中搜索gitee插件并进行下载 TyporapicGo设置Typora 下载Typora进行图像设置 picGogitee设置图床 当我了解picGogitee可以设置图床…

基础论文学习(2)——DETR

目标检测 DETR&#xff1a;End-to-End Detection with Transformer detr是facebook提出的引入transformer到目标检测领域的算法&#xff0c;效果很好&#xff0c;做法也很简单&#xff0c;相较于RCNN和YOLO系列算法&#xff0c;避免了Proposal/AnchorNMS的复杂流程。 1. detr…

网络安全在医疗行业中的重要性

不可否认&#xff0c;现代世界见证了技术和医疗行业的交织&#xff0c;塑造了我们诊断、治疗和管理健康状况的新方式。随着电子健康记录取代纸质文件&#xff0c;远程医疗缩短了患者和医疗服务提供者之间的距离&#xff0c;数字化转型既是福音&#xff0c;也是挑战。最近的全球…

数据库三大范式是什么,又为什么要反范式?

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年6月CSDN上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师…

opencv/C++ 人脸检测

前言 本文使用的测试资源说明&#xff1a; opencv版本&#xff1a;opencv 4.6.0 人脸检测算法 Haar特征分类器 Haar特征分类器是一个XML文件&#xff0c;描述了人体各个部位的Haar特征值。包括&#xff1a;人脸、眼睛、鼻子、嘴等。 opencv 4.6.0自带的Haar特征分类器&…