Reduce size by half
Implement pow(x, n)
Implement pow(x, n).
Analysis
- 假设已知x^n，要求x^2n，那么则只需要一次运算，倒过来我们就可以通过x^n/2，来求pow(x,n). reduce size by half every time。接下来就只需要根据n为奇数或者偶数的不同，进行判断
- better than naive multiplication n times -> O(logn)
corner case when n < 0
只需要将x = 1/x，即可把n变回正值来计算
class Solution { private double fastPow(double x, long n) { if (n == 0) { return 1.0; } double half = fastPow(x, n / 2); if (n % 2 == 0) { return half * half; } else { return half * half * x; } } public double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } return fastPow(x, N); } };
Divide Two Integers
- 核心思路：转化成乘法考虑比较直接。看做divisor * multiple <= dividend. 为了从O(n)优化到O(logn)，multiple的变化为1, 2, 4, ... 2^n
- 在具体实现中，是通过sum的翻倍递增来实现的, sum从divisor开始
ans = ans + recursive(dividend - sum, divisor)
- overflow case:
- anything / 0
- Integer.MIN_VALUE / -1
class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
if (dividend == 0) return 0;
boolean neg = false;
if ((divisor < 0 && dividend > 0) ||
(divisor > 0 && dividend < 0))
neg = true;
long ldivisor = Math.abs((long)divisor);
long ldividend = Math.abs((long)dividend);
int ans = (int)divide(ldividend, ldivisor);
return neg ? -ans : ans;
}
private long divide(long ldividend, long ldivisor) {
if (ldividend == 0 || ldividend < ldivisor) return 0;
long multiple = 1;
long sum = ldivisor;
while (sum + sum <= ldividend) {
sum += sum;
multiple += multiple;
}
return multiple + divide(ldividend - sum, ldivisor);
}
}
Maximum Average Subarray II
Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k. Given nums = [1, 12, -5, -6, 50, 3], k = 3 Return 15.667 // (-6 + 50 + 3) / 3 = 15.667
Analysis
- reduce size by half every time
- 一个数组的子数组的最大平均数一定在数组的最大值和最小值之间，所以二分法的第一步限定average位于[min,max]之中。
- 接下去要做的就是不断的缩小范围，直至max-min足够小（如1e-6），那我们就得到了想要的结果。
- 每一轮设置mid=(min+max)/2，然后将原数组中的每一个数减去这个mid，如果能找到（经过提醒，改正为：大于等于）k个相邻数的总和大于0的情况，那么说明最终结果一定比这个mid要更大，限定下一轮寻找范围在[mid,max]之中。反之在限定在[min,mid]之中。
Find median in 2 sorted Array
1.方法是每次在两个array（合并起来）取前k个，如果平均取，在A中取k/2个，在B中取k/2个，那么比较A和B中这两个位置处的大小可以知道，
- 比较A和B各自选到的数
- if (A[k/2] > B[k/2]) 则知道B中前k/2个肯定是较小的那些，在要取得第k个的时候，肯定是要被抛弃掉的。所以接下来在完整的A和从k/2处开始的B中，找第k-k/2个数，这里不直接用k/2是为了避免奇偶的问题
- if (A[k/2] < B[k/2])
- 因为扔去的是较小的树，所以只需要记录下startIndex
- corner case，需要检查startA + k / 2 - 1是否溢出
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 1)
return findKth(nums1, nums2, 0, 0, len/2+1);
else
return (findKth(nums1, nums2, 0, 0, len/2) + findKth(nums1, nums2, 0, 0, len/2+1)) / 2.0;
}
private double findKth(int[] nums1, int[] nums2, int start1, int start2, int k) {
if (start1 >= nums1.length)
return nums2[start2+k-1];
if (start2 >= nums2.length)
return nums1[start1+k-1];
if (k == 1)
return Math.min(nums1[start1], nums2[start2]);
int key1 = start1+ k / 2 - 1 < nums1.length ? nums1[start1+k/2-1] : Integer.MAX_VALUE;
int key2 = start2+ k / 2 - 1 < nums2.length ? nums2[start2+k/2-1] : Integer.MAX_VALUE;
if (key1 < key2) {
return findKth(nums1, nums2, start1+k/2, start2, k - k/2);
} else {
return findKth(nums1, nums2, start1, start2+k/2, k - k/2);
}
}
2.方法是假设最终的中位数在合并后的数组的k-1,或者k处，这个时候在两个array里，分别取了m1,m2个数。 则有
m1+m2 = k = (n1+n2+1)/2 //n1+n2+1是合并后数组的长度，因为这个时候k是中位数，在这里利用了中位数的性质
接下来的目标就是看如何找到m1。由分析我们可以知道Ck-1必定是Am1-1, Bm2-1中较大的。Ck必定是Am1, Bm2中较小的。于是可以通过Binary Search 来寻找m1，target是Bm2-1
- 注意边界条件有可能m1=0或者n1-1。
- 复杂度是O(log(min(n1,n2)))所以可以在一开始判断两个数组大小，对于较小的数组进行操作
- 注意m1这里是用了几个数，所以二分搜索时候r可以取到n1