4. Median of Two Sorted Arrays (Hard)

https://leetcode.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solutions

1.

class Solution {

    // As a matter of fact, this problem is not that difficult, it should be tagged as easy.

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        int totalLen = len1 + len2;

        int pos1 = totalLen / 2;
        int pos2 = totalLen / 2 + 1;

        if (totalLen % 2 == 1) {
            pos1 = pos2;
        }

        int med1 = 0;
        int med2 = 0;

        int i = 0;
        int j = 0;

        int count = 0;

        while (count < totalLen) {
            while (i < len1 && j < len2) {
                int val;
                if (nums1[i] < nums2[j]) {
                    val = nums1[i++];
                } else {
                    val = nums2[j++];
                }

                count++;
                if (count == pos1) {
                    med1 = val;
                }

                if (count == pos2) {
                    med2 = val;
                }
            }

            while (i < len1) {
                count++;

                if (count == pos1) {
                    med1 = nums1[i];
                }

                if (count == pos2) {
                    med2 = nums1[i];
                }

                i++;
            }

            while (j < len2) {
                count++;

                if (count == pos1) {
                    med1 = nums2[j];
                }

                if (count == pos2) {
                    med2 = nums2[j];
                }

                j++;
            }
        }

        return (med1 * 1l + med2 * 1l) / 2.0;
    }
}

2.

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        int totalLen = len1 + len2;
        boolean isOdd = true;
        if (totalLen % 2 == 0) {
            isOdd = false;
        }

        int[] tmp = new int[totalLen];

        int count = 0;
        int i = 0;
        int j = 0;
        while (count < totalLen) {
            if (i < len1 && j < len2 && nums1[i] <= nums2[j]) {
                tmp[count++] = nums1[i++];
            } else if (i < len1 && j < len2 && nums1[i] >= nums2[j]) {
                tmp[count++] = nums2[j++];
            } else if (j == len2 && i < len1) {
                tmp[count++] = nums1[i++];
            } else if (i == len1 && j < len2) {
                tmp[count++] = nums2[j++];
            }

            // pruning
            if (totalLen >= 3 && count > (totalLen + 1) / 2) {
                break;
            }
        }

        if (isOdd) {
            return tmp[(totalLen - 1) / 2];
        }

        return (tmp[totalLen / 2] * 1l + tmp[totalLen / 2 - 1] * 1l) / 2.0;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-24 22:49:48

results matching ""

    No results matching ""