Gas Station
2017-10-14
加油站问题，LeetCode 链接： https://leetcode.com/problems/gas-station/description/ There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique. 这道题难度为 Medium，但如果对每个加油站进行模拟，则时间复杂度为 $O(n^2)$，OJ 判定超时，而 $O(n)$ 的方法并不容易。 Discuss 区有人给出了 $O(n)$ 的方法： https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas. 但其中用到的结论并没有证明，而且描述不清晰。下面我会说明这两个结论的正确性。 …
求两个有序数组的中位数 Median of Two Sorted Arrays
2017-07-24
这是 LeetCode 上的一道题，求两个有序数组的中位数： https://leetcode.com/problems/median-of-two-sorted-arrays/description/ Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. Follow up: The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. Example 3: Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000 Example 4: Input: nums1 = [], nums2 = [1] Output: 1.00000 Example 5: Input: nums1 = [2], nums2 = [] Output: 2.00000 Constraints: nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106 确定一下输入应满足的条件：两个数组的长度可以有一个为 $0$（此时中位数就是另一个数组的中位数），但不能同时为 $0$。 很容易想到时间复杂度为 $O(m+n)$ 的方法，但是 follow-up 要求复杂度为 $O(\log(m+n))$。从复杂度看应该用分治法。事实上，复杂度可以减少到 $O(\log(\min(m, n)))$。 …