315. Count of Smaller Numbers After Self (Hard)

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Solutions


class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ans = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return ans;
        }

        List<Integer> sorted = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = insert(sorted, nums[i]);

            ans.add(0, index);
        }

        return ans;
    }

    private int insert(List<Integer> sorted, int target) {
        if (sorted.size() == 0) {
            sorted.add(target);

            return 0;
        }

        int left = 0;
        int right = sorted.size() - 1;

        // Do not forget the equal numbers
        if (sorted.get(left) >= target) {
            sorted.add(0, target);

            return 0;
        }

        if (sorted.get(right) < target) {
            sorted.add(target);

            return right + 1;
        }

        // [1,3,3], 3, left 0, right 2
        // [1,3,5,7], 3, left 0, right 4
        // [1,1,1,3,3], 3, left 0, right 4

        while (left < right) {

            // No need to take account of overflow issue
            int mid = (right + left) / 2; // mid=1

            if (sorted.get(mid) < target) {
                left = mid + 1;
            }
            // sorted.get(mid) 3 >= target 3,
            else {
                right = mid - 1; // right=1-1=0
            }
        }

        // to reach here, left == right or left - right == 1
        // mid==left, and right=mid-1

        // [xxx, 1,3,4], left points to 1, right points to 3, insert after 1, left+1
        // [xxx, 1,3,4], left points to 3, left points to 4, edge off 3, left
        int idx = left;
        if (sorted.get(left) < target) {
            idx = left + 1;
        }

        sorted.add(idx, target);

        return idx;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""