Merge Sort - Algorithm

Merge sort
- divide and conquer: left, right, count values while merging left and right

Merge sort code
http://www.jiuzhang.com/solutions/reverse-pairs/
    private int merge(int[] A, int start, int mid, int end) {
        int[] temp = new int[A.length];
        int leftIndex = start;
        int rightIndex = mid + 1;
        int index = start;
        int sum = 0;
        
        while (leftIndex <= mid && rightIndex <= end) {
            if (A[leftIndex] <= A[rightIndex]) {
                temp[index++] = A[leftIndex++];
            } else {
                temp[index++] = A[rightIndex++];
                sum += mid - leftIndex + 1;
            }
        }
        while (leftIndex <= mid) {
            temp[index++] = A[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = A[rightIndex++];
        }
        
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
        
        return sum;
    }

LeetCode 493 - Reverse Pairs
- Merge sort
    private int mergeSort(int[] nums, int s, int e){
        if(s>=e) return 0; 
        int mid = s + (e-s)/2; 
        int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); 
        for(int i = s, j = mid+1; i<=mid; i++){
            while(j<=e && nums[i]/2.0 > nums[j]) j++; 
            cnt += j-(mid+1); 
        }
        Arrays.sort(nums, s, e+1); 
        return cnt; 
    }
- build the Binary Search Tree from right to left and search the partially built tree with nums[i]/2.0
class Node{
    int val, less = 0, same = 1;//less: number of nodes that less than this node.val
    Node left, right;
}


LeetCode 327 - Count of Range Sum
return the number of range sums that lie in [lower, upper] inclusive.
- merge sort
- presum: sum[i..j]
- Binary search tree 
56     private int rangeSize(TreeNode root, long lower, long upper) {
57         int total = root.count + root.leftSize + root.rightSize;
58         int smaller = countSmaller(root, lower);    // Exclude everything smaller than lower
59         int larger = countLarger(root, upper);      // Exclude everything larger than upper
60         return total - smaller - larger;
61     }

Count Inversions in an array
LeetCode 315 - Count of Smaller Numbers After Self
https://discuss.leetcode.com/topic/31554/11ms-java-solution-using-merge-sort-with-explanation
https://discuss.leetcode.com/topic/31162/mergesort-solution/12
int[] count;
public List countSmaller(int[] nums) {
    List res = new ArrayList();     

    count = new int[nums.length];
    int[] indexes = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
     indexes[i] = i;
    }
    mergesort(nums, indexes, 0, nums.length - 1);
    for(int i = 0; i < count.length; i++){
     res.add(count[i]);
    }
    return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
 if(end <= start){
  return;
 }
 int mid = (start + end) / 2;
 mergesort(nums, indexes, start, mid);
 mergesort(nums, indexes, mid + 1, end);
 
 merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
 int mid = (start + end) / 2;
 int left_index = start;
 int right_index = mid+1;
 int rightcount = 0;     
 int[] new_indexes = new int[end - start + 1];

 int sort_index = 0;
 while(left_index <= mid && right_index <= end){
  if(nums[indexes[right_index]] < nums[indexes[left_index]]){
   new_indexes[sort_index] = indexes[right_index];
   rightcount++;
   right_index++;
  }else{
   new_indexes[sort_index] = indexes[left_index];
   count[indexes[left_index]] += rightcount;
   left_index++;
  }
  sort_index++;
 }
 while(left_index <= mid){
  new_indexes[sort_index] = indexes[left_index];
  count[indexes[left_index]] += rightcount;
  left_index++;
  sort_index++;
 }
 while(right_index <= end){
  new_indexes[sort_index++] = indexes[right_index++];
 }
 for(int i = start; i <= end; i++){
  indexes[i] = new_indexes[i - start];
 }
}
- binary search tree

TODO Max Surpasser

LeetCode 327 - Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] sums = new long[n + 1];
    for (int i = 0; i < n; ++i)
        sums[i + 1] = sums[i] + nums[i];
    return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}

private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
    if (end - start <= 1) return 0;
    int mid = (start + end) / 2;
    int count = countWhileMergeSort(sums, start, mid, lower, upper) 
              + countWhileMergeSort(sums, mid, end, lower, upper);
    int j = mid, k = mid, t = mid;
    long[] cache = new long[end - start];
    for (int i = start, r = 0; i < mid; ++i, ++r) {
        while (k < end && sums[k] - sums[i] < lower) k++;
        while (j < end && sums[j] - sums[i] <= upper) j++;
        while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
        cache[r] = sums[i];
        count += j - k;
    }
    System.arraycopy(cache, 0, sums, start, t - start);
    return count;
}


Count Inversions in an array
Count pairs in an array that hold i*arr[i] > j*arr[j]


Find a permutation that causes worst case of Merge Sort


LeetCode 148 - Sort LinkedList
- fake head ListNode fakehead = new ListNode(-1);


X. How to merge
Maximum Sum Path in Two Arrays
We can switch from one array to another array only at common elements.
http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/
if (ar1[i] < ar2[j])
     sum1 += ar1[i++];
 // Add elements of ar2[] to sum2
 else if (ar1[i] > ar2[j])
     sum2 += ar2[j++];

X. K Sorted List
- PriorityQueue

LeetCode 632 - Smallest Range
Find the smallest range that includes at least one number from each of the klists.
- PriorityQueue

LeetCode - Merge k Sorted Lists
Merge K Sorted Iterators - Linkedin
public class IntIter {
    int next;
    Iterator iter;
}


Post a Comment

Labels

Java (159) Lucene-Solr (110) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (12) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Problem Solving (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) System Design (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts