环保局网站建设,百度快照怎么做,开平 做一网站,2022中文无字幕入口网站一、287. 寻找重复数 给定一个包含 n 1 个整数的数组 nums#xff0c;其数字都在 1 到 n 之间#xff08;包括 1 和 n#xff09;#xff0c;可知至少存在一个重复的整数。假设只有一个重复的整数#xff0c;找出这个重复的数。 1、HashMap
在没有其它附加条件的情况下 1 个整数的数组 nums其数字都在 1 到 n 之间包括 1 和 n可知至少存在一个重复的整数。假设只有一个重复的整数找出这个重复的数。 1、HashMap
在没有其它附加条件的情况下读者第一时间会想到通过 HashMap 来记录出现过的数字从而找到重复数 上述实现代码的时间复杂度和空间复杂度都为 O(n)如果只允许使用 O(1) 的空间复杂度该如何解决这道题目呢
2、Binary Search
这种条件下最容易想到的就是通过两重循环暴力搜索当前数字是否与后面的数字重复的方法来解决但是这种方案的时间复杂度为 O(n^2)既然涉及到了搜索就可以尝试通过二分搜索算法将时间复杂度降低到 O(nlogn)。
根据前面的刷题经验可以很容易地找出有序数组1 到 n 的递增整数序列。
接下来的难点就是通过重复数的特性来确定下一轮搜索区间是落在左半区间还是右半区间 首先需要遍历 nums 数组获取不大于当前中间数的数字的个数 如果个数大于中间数那么下一轮搜索区间落在左半区间 如果个数小于中间数那么下一轮搜索区间落在右半区间 二、209. 长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组返回 0。 1、Binary Search
这道题目中的有序数组不太好找需要用到一个技巧构造前缀和数组。 nums [2, 3, 1, 2, 4, 3]# 前缀和sums [0, 2, 5, 6, 8, 12, 15]从而上述示例中可以发现前缀和数组是一个有序数组那么对于任意 i 到 j 的连续子数组之和可以通过 sums[j1] - sums[i] 求出。
并且根据前缀和的差值与 s 的比较可以判断满足条件的连续子数组的终止下标落在哪个区间内。 参考视频传送门
通过前缀和对数组的预处理以及二分搜索算法时间复杂度为 O(nlogn)。
2、Two Points
除了上述二分搜索算法的处理方法之外可能最简单暴力的方法就是通过嵌套循环找出长度最小的连续子数组但是这种方法的时间复杂度为 O(n^2)有没有方法将其降低到 O(n) 的时间复杂度呢。
这里就要提及一下滑动窗口算法它常用于处理连续子元素问题将嵌套循环问题转化为单循环问题。 在本题中通过头指针和尾指针维护当前连续子数组的和值窗口 当前窗口的和值大于 s 那么头指针向后移动一位 当前窗口的和值小于 s 那么尾指针向后移动一位 三、153. 寻找旋转排序数组中的最小值 假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。 这一类型的题目在 Easy 中也出现过如【852. 山脉数组的峰顶索引】和【162. 寻找峰值】。
本题中原本的递增数组被转化成包含两个递增序列的数组并且其中无重复元素那么就可以得出第一个递增数组中的任意一个元素都大于第二个递增数组中的元素。
有了这一关键信息对于任一中间数都可以将其与当前搜索区间的最后一个元素相比较从而知道当前中间数在哪一个递增序列上而所求的最小值存在于第二个递增序列的头部那么不断将搜索区间往这一方向收缩即可得到最小值 四、33. 搜索旋转排序数组 假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值如果数组中存在这个目标值则返回它的索引否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。 这道题是【153. 寻找旋转排序数组中的最小值】的进阶题型。
在 153 中只需要将搜索区间不断向第二个递增区间收缩即可得到最小值。而本题中的目标值的位置并不确定所以在每次确定搜索区间时需要考虑很多种情况 如果当前搜索区间只落在一个递增区间上那么和一般的处理方法没什么异样 如果当前搜索区间横跨两个递增区间那么就需要根据中间数在第一个递增区间还是第二个递增区间上分别处理
具体的条件判断请查看下面的代码实现 五、81. 搜索旋转排序数组 II 假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true否则返回 false。 这道题目在【33. 搜索旋转排序数组】的基础上去除了”不存在重复元素“这一条件。
回顾 33 题的解法在寻找下一个搜索区间时通过该搜索区间的头部元素和尾部元素的比较得出当前搜索区间是否横跨两个递增序列。一旦没有无重复元素这一条件那么根据头尾两个元素无法判断当前搜索区间是否横跨两个递增序列。
本题要求计算元素的存在性那么一个元素的重复元素对其存在性是没有任何影响的所以只要在二分搜索的过程中剔除掉头尾部的重复元素即可 写在最后
算法作为计算机的基础学科用 JavaScript 刷一点也不丢人εεε┏(゜ロ゜;)┛。
本系列文章会分别给出一种算法的3种难度的总结篇简单难度中等难度以及困难难度。在简单难度中会介绍该算法的基本知识与实现另外两个难度着重讲解解题的思路。
如果本文对您有所帮助可以点赞或者关注来鼓励博主。
