恋上数据结构与算法第三季课程笔记01
2022/1/9 17:05:19
本文主要是介绍恋上数据结构与算法第三季课程笔记01,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
注:有的图参来源于网络资源
1._88合并两个有序数组
标签:归并排序,三指针
思路:设置三个指针,分别指向实际数组一的尾部 i1、数组i2、整体数组的尾部i3。
每次比较i1和i2指向的值,若i2 > i1,则将i2指向的值与i3指向的值交换,同时i2--,i3--.
若i2 <= i1,则将i1指向的值与i3指向的值交换,同时i1--,i3--.
终止条件:i2指向的指针减至0.
注意点:1.清楚在什么条件下排序可终止?
当i2减至0时,表明排序结束。当i1减至0时,表明数组一已经排序完毕,将数组二的值直接赋给整体数组即可。
2.从什么方向开始排序?
从右边开始排序,不会对原来的元素覆盖。
代码:
public void merge(int[] nums1, int m, int[] nums2, int n) { int i1 = m - 1; int i2 = n - 1; int i3 = m + n - 1; while(i2 >= 0){ if(i1 >= 0 && nums2[i2] < nums1[i1]){ nums1[i3--] = nums1[i1--] ; }else{ nums1[i3--] = nums2[i2--] ; } } }
2._75颜色分类
标签:数组,三指针
思路:注意题目要求仅使用常数空间的一趟扫描算法。即要求空间复杂度为O(1),时间复杂度为O(n)。虽然题目看起来像是在做排序,但是有了这些条件后,我们已经学过的排序算法均不符合条件,都被排除掉。
可以用三个指针来解答。三个指针分别指向数组的最左边(左指针left)、最右边(右指针right)、从最左边开始遍历整个数组(遍历指针i)。
首先,判断遍历指针i指向的值0,如若为0,i指向的值和left指向的值交换,i++,left++,
如若为1,i++,left不动。
如若为2,i指向的值和right指向的值交换,right--,i值不变
终止条件:i > right(left是指向左边已经排序好的,right指向右边排序好的)
注意点:1.终止条件
2.先思考好每一步指针应该做怎样的改变
代码:
public void sortColors(int[] nums) { int left = 0,i = 0; int right = nums.length - 1; while(i <= right){ if(nums[i] == 0){ swap(nums,i++,left++); }else if(nums[i] == 1){ i++; }else{ swap(nums,i,right--); } } } private void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
3._16部分排序
标签:数组,双指针
思路:首先要理解题意,需要排序的是逆序对,我们只需要找到最左边和最右边的逆序对位置。
- 分别
从左往右
和从右往左
找到逆序对
,这样即可确定范围。 从左往右
扫描,记录最大值
,如果发现当前值
小于最大值
,则记录它的位置(有可能是逆序对
最大范围),如果当前值
大于最大值
,则覆盖最大值
。从右往左
扫描,记录最小值
,如果发现当前值
大于最小值
,则记录它的位置(有可能是逆序对
最大范围),如果当前值
小于最小值
,则覆盖最小值
。- 两次扫描记录的位置范围,就是需要排序的范围。
注意点:1.遇到相等情况是否需要记录?
代码:
public int[] subSort(int[] array) { if(array.length == 0) return new int[]{-1,-1}; int max = array[0]; int min = array[array.length - 1]; int leftIndex = -1,rightIndex = -1; //把变量的值初始化为-1,可以避免后来判断 for(int i = 1;i < array.length;i++){ //从左往右,正序是越来越大,逆序是越来越小,需要找最右边的逆序对 if(array[i] >= max){ max = array[i]; }else{ rightIndex = i; } } //提前结束 if(rightIndex == -1) return new int[]{-1,-1}; for(int i =array.length - 2;i >=0 ;i--){ //从右往左,正序是越来越小,逆序是越来越大,需要找最左边的逆序对 if(array[i] <= min){ min = array[i]; }else{ leftIndex = i; } } return new int[]{leftIndex,rightIndex}; }
这篇关于恋上数据结构与算法第三季课程笔记01的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?