5.24号刷题

发表于 | 分类于 | 0 comments

第一题 4. Median of Two Sorted Arrays

####算法
left_part | right_part
A[0], A[1], …, A[i-1] | A[i], A[i+1], …, A[m-1]
B[0], B[1], …, B[j-1] | B[j], B[j+1], …, B[n-1]
我们可以将数组A, B分成两份，当满足

1) len(left_part) == len(right_part)
2) max(left_part) <= min(right_part)

即

(1) i + j == m - i + n - j (or: m - i + n - j + 1)
    if n >= m, we just need to set: i = 0 ~ m, j = (m + n + 1)/2 - i
(2) B[j-1] <= A[i] and A[i-1] <= B[j]

的时候，说明i和j已经满足要求
i 的取值范围是0 ~ A.length, j 的取值为 (m + n + 1) / 2 - i。这样的话i + j的和是与上面式子相等的。
之后接下来的步骤采用二分查找寻找合适的i值

<1> Set imin = 0, imax = m, then start searching in [imin, imax]

<2> Set i = (imin + imax)/2, j = (m + n + 1)/2 - i

<3> Now we have len(left_part)==len(right_part). And there are only 3 situations
     that we may encounter:
    <a> B[j-1] <= A[i] and A[i-1] <= B[j]
        Means we have found the object `i`, so stop searching.
    <b> B[j-1] > A[i]
        Means A[i] is too small. We must `ajust` i to get `B[j-1] <= A[i]`.
        Can we `increase` i?
            Yes. Because when i is increased, j will be decreased.
            So B[j-1] is decreased and A[i] is increased, and `B[j-1] <= A[i]` may
            be satisfied.
        So we must `increase` i. That is, we must ajust the searching range to
        [i+1, imax]. So, set imin = i+1, and goto <2>.
    <c> A[i-1] > B[j]
        Means A[i-1] is too big. And we must `decrease` i to get `A[i-1]<=B[j]`.
        That is, we must ajust the searching range to [imin, i-1].
        So, set imax = i-1, and goto <2>.

对于特殊情况，例如A, B为空，或者中位数集中在某一边，我们可以进行if, else 的处理。对于0 的情况，最大值对应的是另一个的[i-1]或[j-1]。对于全部其中在另一个的情况，最小值是另一个的[i]或[j]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class findMedianSortedArrays4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (n < 0 || m < 0) return 0.0;
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        int imin = 0, imax = m, half = (m + n + 1) / 2, maxLeft = 0, minRight = 0;
        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = half - i;
            //case 1 B[j-1] > A[i]
            if (i < m && nums2[j-1] > nums1[i]) {
                imin = i + 1;
            // case 2 A[i-1] > B[j]
            } else if (i > 0 && nums1[i-1] > nums2[j]) {
                imax = i -1;
            // case 3 i is perfect
            } else {
                if (i == 0) maxLeft = nums2[j-1];
                else if(j == 0) maxLeft = nums1[i-1];
                else maxLeft = Math.max(nums2[j-1], nums1[i-1]);
                if ((n + m) % 2 == 1) return maxLeft;
                if (i == m) minRight = nums2[j];
                else if (j == n) minRight = nums1[i];
                else minRight = Math.min(nums1[i], nums2[j]);
                return (minRight + maxLeft) / 2.0;
            }
        }
        return 0.0;
    }
}

学到的东西

由于这道题用到了二分查找，所以自己也补充的正确的二分查找的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
public class BinarySearch {
    public static int BinarySearch (int[] nums, int key) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;  //if (high + low) => 超过int 2^30次方，会发生溢出，如果用减的话会更好，化简之后是一样的
            System.out.println("low:" + low +" high:" + high + " mid:" + mid + " number:" + nums[mid]);
            if (nums[mid] > key) high = mid - 1;
            else if (nums[mid] < key) low = mid + 1;
            else return mid;
        }
        return -1;
    }
}

注意一点，上下界的更新不是mid,是mid - 1 和 mid + 1

第二题 153. Find Minimum in Rotated Sorted Array

算法

基于Bindary Search 改进了搜索的算法。判断条件是最终如果两个之间差为1的话，那么表示刚好遇到突变的那个值，进行输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class findMin153 {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int min = 0, max = nums.length - 1;
        if (nums[max] >= nums[min]) return nums[min];  // The nums is ascending.
        while (max >= min) {
            int middle = min + (max - min) / 2;
            if (nums[min] > nums [middle]) max = middle;
            else if(nums[min] < nums [middle]) min = middle;
            if (max - min == 1) return nums[max];
        }
        return nums[0];
    }
}

学到的东西

对一个数组进行合法性的验证

if (nums == null || nums.length == 0) return 0;

第三题 11. Container With Most Water

算法

每次移动较短的那个，最后通过这样的方法可以保证最大的值是一定被遍历到的。具体证明需要反证法链接

1
2
3
4
5
6
7
8
9
10
11
public class maxArea11 {
    public int maxArea(int[] height) {
        int begin = 0, end = height.length - 1, maxS = 0;
        while (begin <= end) {
            maxS = Math.max(maxS, (end - begin) * Math.min(height[begin], height[end]));
            if (height[begin] > height[end]) end--;
            else begin++;
        }
        return maxS;
    }
}