Leetcode: Kth Largest Element in an Array (4ms)

Difficulty: Medium

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the 

sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Divide and Conquer Heap

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

Basically using the similar procedure in Quick Sort.
The good thing here is that we don't need to sort the whole array, we only need to sort part of the array until we found the Kth biggest one by revising the Quick Sort a little bit. So in the codes, we revised the quick sort to fit this problem.

NOTE: the quick should use pointers to transport the array, otherwise the space will exceed the limit.

/////////////////////////////////////////////
//codes

class Solution {

 public:

        //revised quick sort

        vector<int> QuickSort(vector<int>& s, int first, int last, int k){

               // s[first, last] -- is part of the data in s that needs to be sorted.

               int lower = first + 1, upper = last, bound = s[(last + first) / 2], len = s.size();

               //put the bound (middle one) in the first place

               //to ensure that it's not moved around. Later it

               //will be moved back

               swap(s[first], s[(last + first) / 2]);

               //swap according to bound

               while (lower <= upper){

                      while (s[lower] < bound){

                            lower++;

                      }

                      while (s[upper] > bound){

                            upper--;

                      }

                      if (lower < upper) swap(s[lower++], s[upper--]);

                      else lower++;

               }

               //move bound back to it's proper position

               swap(s[first], s[upper]);

               //partition and call quicksort, the previous bound is not counted in.

               if (first < upper - 1 && k>len - upper) s = QuickSort(s, first, upper - 1, k);

               if (upper + 1 < last && k<len - upper) s = QuickSort(s, upper + 1, last, k);

               return s; //up to now, the input s has been sorted!

        }

        //-----------------------------------------------

        int findKthLargest(vector<int>& nums, int k) {

               vector<int> fn = QuickSort(nums, 0, nums.size() - 1, k);

               return fn[nums.size() - k];

        }

 };

Leetcode: Merge k sorted linked lists

Difficulty: Hard

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Subscribe to see which companies asked this question

Hide Tags

 Divide and Conquer Linked List Heap

Show Similar Problems

---------------------------------------------
To merge K sorted linked lists, similar like the procedure in later part of merge sort:
including
1). merge two sorted lists;
2). divide K lists into small lists until 1 or 2 lists in order to use 1) (Divide and Conquer); here backtracking is used.

NOTE: If only use 1), e.g., merge 1 and 2 lists then merge 3......until the last one, this way will exceed the time constrain.

NOTE**: subList1.assign(it, it + subList.size() / 2);//assign not include the last one: [first,last)

assign doesn't include the last!!

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

class Solution {

 public:

        //merge two lists

        ListNode* mergeList(ListNode*a, ListNode*b){

               ListNode* dum = new ListNode(-1), *tmp = dum;

               //check input

               if (a == NULL)return b;

               if (b == NULL)return a;

               //merge two lists

               while (a != NULL || b != NULL){

                      if (a == NULL){

                            tmp->next = b;

                            break;

                      }

                      else if (b == NULL){

                            tmp->next = a;

                            break;

                      }

                      else if (a->val<b->val){

                            tmp->next = a;

                            a = a->next;

                            tmp = tmp->next;

                      }

                      else{

                            tmp->next = b;

                            b = b->next;

                            tmp = tmp->next;

                      }

               }

               tmp = dum->next;

               delete dum;

               return tmp;

        }

        //backtracking to devide K lists into small untill two or one list

        ListNode* mergeBackTrac(vector<ListNode*> subList){

               ListNode* tmp = NULL, *tmp1 = NULL, *tmp2 = NULL;

               if (subList.size() == 0)return tmp;

               else if (subList.size() == 1){

                      tmp = mergeList(subList[0], tmp);

               }

               else if (subList.size() == 2){

                      tmp = mergeList(subList[0], subList[1]);

               }

               else{

                      std::vector<ListNode*>::iterator it = subList.begin();

                      vector<ListNode*> subList1;

                      subList1.assign(it, it + subList.size() / 2);//assign not include the last one: [first,last)

                      vector<ListNode*> subList2;

                      subList2.assign(it + subList.size() / 2, subList.end());

                      tmp1 = mergeBackTrac(subList1);

                      tmp2 = mergeBackTrac(subList2);

                      tmp = tmp = mergeList(tmp1, tmp2);

               }

               return tmp;

        }

        //main function

        ListNode* mergeKLists(vector<ListNode*>& lists) {

               ListNode* dP = NULL;

               dP = mergeBackTrac(lists);

               return dP;

        }

 };

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;

        }

 };