Max Surpasser - Algorithms and Problem SolvingAlgorithms and Problem Solving

Max Surpasser - Algorithms and Problem SolvingAlgorithms and Problem Solving

For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it. Given an array of integers, Output the max number of surpassers.

For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn't have any surpasser.
Basically, we need to get the number of surpassers of every element and finally output the max of them. For example, The max number of surpassers for {10,3,4,5,2} is 2 as 3 has 2 surpassers.

Note that if the array is sorted in decreasing order than number of surpassers for position i = i-1. This signals us that we can do better by sorting the array while saving the position of each element in the original array. Also, another important observation is that if we split the array into two halves such that both halves are sorted in decreasing order then we can compute left partitions surpassers by using solution of right partition by merging them in the following way –

• Left[i] < Right[j]: then Right[j] is a surpasser for Left[i]. We can keep accumulate number of surpassers for Left[i] on the right partition as long as the condition is valid for q<=j<=r , where q is the partition index and r in the high end index.
• Left[i] >= Right[j]: then Right[j..] can’t be part of the surpasser for Left[i]. So, we can update number of surpassers by adding the accumulated surpasser in the previous step.

Essentially there are three parts of this approach –

• Divide: We can keep halving the array recursively until we see one element.
• Conquer: We get each of the subproblems of one element and solve it right away because we know that number of surpasser for these smallest subproblem (i.e. with only one element) is 0.
• Accumulate: Now, we accumulate results from the conquered i.e. solved subproblems. We accumulate by merging as described previously.

How to implement the approach? We might have already figured out this sounds like a merge sort. It is indeed exactly merge sort in decreasing order while maintaining the surpasser. Following is a simple Merge Sort modification which sorts the given array “A” in decreasing order, but in spite of modifying given array it modifies the an array of indexes “rank”, which allows to track surpassers in the third array “surp”.
Time: O(n log n).
Space: O(n).

public static class MaxSurpasser {
    int[] A, rank, surp, mergedRank;

    private MaxSurpasser(int[] a) {
        this.A = a;
        this.rank = new int[a.length];
        this.surp = new int[a.length];
        this.mergedRank = new int[a.length];
        for (int i = 0; i < rank.length; i++){
            rank[i] = i;
        }
    }

    public static int find(int[] a) {
        return new MaxSurpasser(a).sort();
    }

    private int sort() {
        mergeSort(0, A.length - 1);
        int max = 0;
        System.out.print("bigger on rights count: ");
        for (int i = 0; i < A.length; i++) {
         System.out.print(surp[i]+", ");
            if (surp[i] > max) {
                max = surp[i];
            }
        }
        System.out.println();
        return max;
    }

    private void mergeSort(int l, int r) {
        if (l >= r) {
            return;
        }
        //divide
        int q = (l + r) / 2;
        mergeSort(l, q);
        mergeSort(q + 1, r);
        //conquer
        int i = l;
        int j = q + 1; int acc = 0;
        //accumulate through merge
        for (int s = l; s <= r; s++) {
         if (j <= r && (i > q || A[rank[i]] < A[rank[j]])){
                mergedRank[s] = rank[j];
                acc++;
                j++;
            }
         else{
          mergedRank[s] = rank[i];
                surp[rank[i]] += acc;
                i++;
         }
        }
        for (int s = l; s <= r; s++) {
            rank[s] = mergedRank[s];
        }
    }
}

https://discuss.leetcode.com/topic/50996/surpasser-number
This looks a lot like 315. Count of Smaller Numbers After Self, with "smaller" replaced with "greater" instead.
http://www.geeksforgeeks.org/find-surpasser-count-of-each-element-in-array/

http://www.fgdsb.com/2015/01/11/maximal-surpasser-count/
利用特殊数据结构的话，本题有很多种做法，比如BST，线段树，点树，树状数组。下面给出一种归并排序思路的解法。实际上跟Inverse Pairs基本是完全一样的。这里关心的是顺序而不是逆序。
大体思路就是在降序归并排序的过程中每次遇到顺序对就记录下来，比如merge的过程中两个元素分别是3和7，3 < 7，所以3的顺序数+1。最后merge sort完毕后，每个顺序数的个数我们都知道，返回最大值即可。
思路很简单，唯一tricky的地方就是每次遇到顺序的时候，这个顺序数的个数到底加多少。这个需要注意一下。

用BST的话也很简单，注意每个节点要存surpasser的数量，O(NlogN)建树，然后O(N)遍历一遍找到最大值即可。注意tricky的地方是BST的定义是不允许有重复的，而这题的输入数组是有重复的，要处理一下这个情况。

int max_surpasser(vector<int> nums) {

vector<int> temp(nums.size());

int ret = 0;

unordered_map<int, int> counts;



auto merge = [&](int left, int mid, int right) {

if(left >= right) return;

int l = mid, r = right, cur = right;

while (l >= left && r > mid) {

if(nums[l] < nums[r]) {

counts[nums[l]] += r - mid;

ret = max(ret, counts[nums[l]]);

temp[cur--] = nums[l--];

} else {

temp[cur--] = nums[r--];

}

}

while(l >= left) temp[cur--] = nums[l--];

while(r > mid) temp[cur--] = nums[r--];       

copy(temp.begin()+left, temp.begin()+right+1, nums.begin()+left);

};

function<void(int,int)> sort = [&](int left, int right) {

if(left >= right) return;

int mid = left + (right - left) / 2;

sort(left, mid);

sort(mid + 1, right);

merge(left, mid, right);

};

sort(0, (int)nums.size() - 1);

return ret;

}

This is O(n^2) solution.

• For every element, we scan all elements behind it and maintain a ns as its number of surpassers.
• If one element is larger, then we increase the ns.
• After we finish on all elements, the max of all the nses is what we are looking for.

http://jsolved.blogspot.com/2016/07/surpasser-count-of-each-element-in-array.html
??? strange implementation
Read full article from Max Surpasser - Algorithms and Problem SolvingAlgorithms and Problem Solving