4.md

4. Median of Two Sorted Arrays

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

R2

class Solution { public int lengthOfLongestSubstring(String s) { int[] check = new int[256]; int res = 0, start = 0, end = 0; while (end < s.length()) { if (check[s.charAt(end)] == 0) { check[s.charAt(end)] = 1; end++; res = end - start > res ? end - start : res;
} else { while (start < s.length() && s.charAt(start) != s.charAt(end)) { check[s.charAt(start++)] = 0; } check[s.charAt(start++)] = 0; } } return res; } }

R1

my thoughts:

1. merge and select median, O(m+n)

2. find median of nums1, compare with median of nums2, binary cut both according the result. Ideally O(log(m+n)) but did not implement into code.

3. cut nums1 into two halves, the first half of the merged array will be first half of nums1 plus (len1 + len2)/2 - len(first half of 1); check if the cut satisfy 'merged first half <= merged rest' if not binary search cut nums1; Tricky part is to handle the edges, where cut nums1 into empty array and nums1 or nums1 and empty array. O(log(min(m,n)))

my solution:

**********123ms
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        l1, l2 = len(nums1), len(nums2)
        if not nums1:
            return (nums2[l2/2] + nums2[(l2-1)/2])/2.0
        lo, hi = 0, l1
        l = l1 + l2
        while True:
            r1 = (lo + hi)/2
            r2 = l/2-r1
            
            L1 = (-sys.maxint-1) if r1==0 else nums1[r1-1]
            R1 = sys.maxint if r1==l1 else nums1[r1]
            L2 = (-sys.maxint-1) if r2==0 else nums2[r2-1]
            R2 = sys.maxint if r2==l2 else nums2[r2]
            #print r1, r2, L1, R1, L2, R2
            if L1<=R2 and L2<=R1:
                return float(min(R1, R2)) if l%2 else (max(L1,L2)+min(R1,R2))/2.0
            elif L1>R2:
                hi = r1
            elif L2>R1:
                lo = r1+1

my comments:

for some reason, merge the two arrays and find median is faster...

from other ppl's solution:

1. better handling of the edges, 102ms:
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        A,B=nums1,nums2
        m, n = len(A), len(B)
        if m > n:
            A, B, m, n = B, A, n, m
        if n == 0:
            raise ValueError

        imin, imax, half_len = 0, m, (m + n + 1) / 2
        while imin <= imax:
            i = (imin + imax) / 2
            j = half_len - i
            if i < m and B[j-1] > A[i]:
                # i is too small, must increase it
                imin = i + 1
            elif i > 0 and A[i-1] > B[j]:
                # i is too big, must decrease it
                imax = i - 1
            else:
                # i is perfect

                if i == 0: max_of_left = B[j-1]
                elif j == 0: max_of_left = A[i-1]
                else: max_of_left = max(A[i-1], B[j-1])

                if (m + n) % 2 == 1:
                    return max_of_left

                if i == m: min_of_right = B[j]
                elif j == n: min_of_right = A[i]
                else: min_of_right = min(A[i], B[j])

                return (max_of_left + min_of_right) / 2.0