智林东莞网站建设公司,网络营销的推广策略,滨州建网站,怎样说服老板做网站文章目录 前言数组中出现超过一半的数字数组中只出现一次的数字颜色的分类问题(荷兰国旗问题)基于冒泡排序的双指针#xff08;快慢指针#xff09;基于快排的双指针#xff08;对撞指针#xff09; 总结 前言 提示#xff1a;苦不来自外在环境中的人、事、物#xff0c;… 文章目录 前言数组中出现超过一半的数字数组中只出现一次的数字颜色的分类问题(荷兰国旗问题)基于冒泡排序的双指针快慢指针基于快排的双指针对撞指针 总结 前言 提示苦不来自外在环境中的人、事、物只是自内的妄想和执着。 --金惟纯 这里整理一些比较经典的题目巩固一下数组的学习。 数组中出现超过一半的数字
题目介绍参考剑指 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;}HashMapInteger, 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是一种用于在数组或列表中查找出现次数超过一半的元素的算法。该算法基于以下观察如果一个元素出现次数超过一半那么它在数列中出现的次数一定比其他所有元素出现次数之和还要多。
算法步骤如下
初始化两个变量候选元素candidate和计数器count候选元素用于保存当前被选中的元素计数器用于统计候选元素的出现次数。遍历整个数组或列表对于每一个元素 如果计数器为0将当前元素设为候选元素将计数器设为1。否则如果当前元素与候选元素相同计数器加1否则计数器减1。 完成遍历后最后留下的候选元素就是候选元素但这并不代表它一定是超过一半的元素只是候选元素的可能性更高。最后再次遍历整个数组或列表统计候选元素的出现次数。如果它的出现次数确实超过一半那么它就是超过一半的元素否则不存在超过一半的元素。
下面给出一个例子来解释摩尔投票法 假设我们有一个数组[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;}QA
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];}HashSetInteger 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也称为“排他性或”操作是一种逻辑运算用于比较两个值的不同之处。异或操作有以下几条规则
同一个值与自身进行异或操作结果为0A ⊕ A 0任意值与0进行异或操作结果不变A ⊕ 0 A异或操作满足交换律A ⊕ B B ⊕ A异或操作满足结合律(A ⊕ B) ⊕ C A ⊕ (B ⊕ C)异或操作满足自反性A ⊕ B ⊕ A B
举例来说明
与自身进行异或操作7 ⊕ 7 0与0进行异或操作5 ⊕ 0 5交换律3 ⊕ 5 5 ⊕ 3结合律(2 ⊕ 4) ⊕ 6 2 ⊕ (4 ⊕ 6)自反性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)
这个问题很典型双指针问题当然可以采用多种方式的双指针解决我们研究第一种与冒泡类似的第二种与快排类似。
基于冒泡排序的双指针快慢指针
冒泡排序我们都知道就是根据大小逐步和后面的比较慢慢调整到整体有序的状态这种方法是比较稳定的排序方法。
当然我们可以这样考虑
第一次遍历我们将数组中所有0交换到数组的头部第二次遍历只需要处理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左侧的元素都是0right指针便是right右侧的元素都是2index指针从头到尾遍历数组根据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;}}}总结
注意双指针问题边界和条件。
