209. 长度最小的子数组

题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例:  输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 解法1 – 朴素算法O(n^2) 解法1使用朴素算法,我们使用指针i, j(0<=i<=j<|nums|)来描述子数组,然后计算i到j区间元素到和,如果大于等于s则取j – i + 1作为可能到解ans;如果小于s则j右移。为了实现O(1)时间复杂度的区间求和,我们可以使用prefix sum算法预先计算前缀和。当指针i和j扫描完所有的连续区间,我们取最小的解就是答案。如果找不到子数组当和大于等与s,就返回0。 需要注意一点,当找到一对i, j我们就可以退出内层循环。因为继续找下去的子序列长度已定大于(i-j+1),否则会TLE。算法的时间复杂度为O(n^2),空间复杂度为O(n) (存放前缀和)。全部代码如下: 解法2 – 优化的朴素算法O(nlogn) 我们沿用解法1的思路,但是对寻找连续区间上进行优化。我们让i = [0, |nums|),使用二分搜索寻找j,其中i <= j < |nums|。因为我们有前缀和数组prefix,我们可以在O(logn)的时间内找到一个下界(lower bound),使得prefix[j] – prefix[i] >= s。那么,j – i +1就是其中一个解,当i遍历完整个数组时,就取最小的那个解作为答案。…

Read more

4. 寻找两个有序数组的中位数

题目描述 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ 解法1 解法1使用Binary Search。考虑两个排序数组nums1与nums2,合并后后形成有序数组nums。记|nums1| = n1, |nums2| = n2, |nums| = n, 有n = n1 + n2。对nums求中位数,那么需要取nums的第k个数(n是奇数)或与第k+1个数取平均(n是偶数),其中k =…

Read more

275. H指数 II

题目描述 给定一位研究者论文被引用次数的数组(被引用次数是非负整数),数组已经按照升序排列。编写一个方法,计算出研究者的 h 指数。 h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)至多有 h 篇论文分别被引用了至少 h 次。(其余的 N – h 篇论文每篇被引用次数不多于 h 次。)” 示例: 输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。   由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。 说明: 如果 h 有多有种可能的值 ,h 指数是其中最大的那个。 进阶: 这是 H指数 的延伸题目,本题中的 citations 数组是保证有序的。 你可以优化你的算法到对数时间复杂度吗? https://leetcode-cn.com/problems/h-index-ii/ 解法1 本题目和274. H指数的区别是,文章已经按照应用次数排序。此外,题目要求优化到对数时间复杂度,很自然能联想到Binary Search。…

Read more