Leetcode: Median of Two Sorted Arrays

Difficulty: Hard

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)).

Subscribe to see which companies asked this question

Hide Tags

 Divide and Conquer Array Binary Search

--------------------------------------------------

//Binary search with two arrays
// l1, m1, r1;
// l2, m2, r2;
// try to find the Kth elements using binary search: keep the most left part while discard the most right part (there are total 4 parts in each round)


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1=nums1.size(), size2=nums2.size(), size=size1+size2, k=size/2;
        int l1=0, l2=0, r1=nums1.size()-1, r2=nums2.size()-1, m1=(l1+r1)/2, m2=(l2+r2)/2;
        int even=size%2, cnt=0;//even==0 is even
        //corner case
        //if(size1==0)....
        //if(size2==0)....
        int max=nums1[0]>nums2[0]?nums2[0]:nums1[0], max_pre=max;
        //normal cases    
        while(true){
            if(nums1[m1]>nums2[m2]){
                cnt+=m2-l2+1;
                l2=m2+1;
                m2=(l2+r2)/2;
                //
                r1=m1; 
                m1=(l1+r1)/2;
                max_pre=max;
                max=max>nums2[m2]?max:nums2[m2];
            }
            else{
                cnt+=m1-l1+1;
                l1=m1+1;
                m1=(l1+r1)/2;
                //
                r2=m2;
                m2=(r2+l2)/2;
                max_pre=max;
                max=max>nums1[m1]?max:nums1[m1];
            }
            //
            if(cnt==k && even ==0 ) return (max+max_pre)/2;
            if(cnt==k && even ==1 )return max;      
        }
    }

};














Merge the two and find the Kth element. 

Don't need to merge all, only need to merge the first Kth element. 

//////////////////////////////////////////////////////

//codes:

class Solution {

 public:

        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

               int len1 = nums1.size(), len2 = nums2.size(), i = 0, j = 0, mid1 = 0, mid2 = 0, count = 0;

               //check input

               if (len1 + len2 == 0)return NULL;

               while (1){

                      count++;

                      if (count == (len1 + len2) / 2){

                            if (i == len1) { mid1 = nums2[j]; j++; }

                            else if (j == len2) { mid1 = nums1[i]; i++; }

                            else if (nums1[i]<nums2[j]) { mid1 = nums1[i]; i++; }

                            else { mid1 = nums2[j]; j++; }

                            continue;

                      }

                      else if (count == (len1 + len2) / 2 + 1){

                            if (i == len1) { mid2 = nums2[j]; j++; }

                            else if (j == len2) { mid2 = nums1[i]; i++; }

                            else if (nums1[i]<nums2[j]) { mid2 = nums1[i]; i++; }

                            else { mid2 = nums2[j]; j++; }

                            break;

                      }

                      //updtate the index

                      if (i == len1) { j++; }

                      else if (j == len2) { i++; }

                      else if (nums1[i]<nums2[j]) { i++; }

                      else { j++; }

               }

               //calculate median

               double fn = (len1 + len2) % 2 == 0 ? double(mid1 + mid2) / 2 : mid2;

               return fn;

        }

 };

Leetcode: Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Hide Tags

 Linked List

-----------------------------------------------------------------

As the pointer of list can't move backward, double pointers method scan from two end to the center doesn't work. So we need to think about way to do it with an forward direction. Following is one of such method:

1. locate the middle of the list: 

    there are two kinds, odd and even number of nodes, the middle one should be calculated differently. 

2. reverse the order for all the nodes in right side of middle node. For how to reverse the whole linked list, check there. 

3. merge the list with forward order. 

when number of node is even, the procedure is shown below:

when number of node is odd, the procedure is shown as:

////////////////////////////////////////////////

////code

class Solution {

public:

       void reorderList(ListNode* head) {

              //check input

              if (head == NULL || head->next == NULL || head->next->next == NULL) return;

              //find the middle and final location

              int len = 1, midLen = 0;

              ListNode *mid = head, *final = head, *tmp = head, *left = head;

              while (mid->next != NULL) { len++; mid = mid->next; }

              final = mid;

              mid = head;

              //locate the mid

              midLen = (len % 2) == 1 ? len / 2 + 1 : len / 2;

              for (int i = 1; i<midLen; i++){

                     mid = mid->next;

              }

              tmp = mid;

              //reverse the right half list

              ListNode* cur = tmp->next;

              ListNode* pre = cur->next;

              cur->next = NULL;//the final node after reverse

              while (pre != NULL)

              {

                     ListNode* temp = pre->next;

                     pre->next = cur;

                     cur = pre;

                     pre = temp;

              }

              tmp->next = cur;

              //reorder the list

              mid = tmp;

              for (int i = 1; i <= len - midLen; i++){

                     tmp = left->next;

                     left->next = mid->next;

                     mid->next = mid->next->next;

                     left->next->next = tmp;

                     //update pointers

                     left = left->next->next;

                     if (left == mid)break;

              }

              return;

       }

};