Count of Smaller Number I && II

Count of Smaller Number I 

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller that the given integer.

Example

For array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]

Note

We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge

Could you use three ways to do it.

  1. Just loop
  2. Sort and binary search
  3. Build Segment Tree and Search.

Solution:  Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>

public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
    //Version 1. sort + binary search
    //Version 2. Segment Tree. not as efficient as version 1.
    //check <Count of Smaller Number before itself>
    ArrayList<Integer> result = new ArrayList<>();
    if (A == null || queries == null) {
        return result;
    }
    if (A.length == 0) {
        for (int i = 0; i < queries.length; i++) {
            result.add(0);
        }
        return result;
    }
    Arrays.sort(A);
    for (int i = 0; i < queries.length; i++) {
        int target = queries[i];
        //find the last element A[i]<target, i+1 is the number
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] < target) {
            result.add(end + 1);
        } else if (A[start] < target) {
            result.add(start + 1);
        } else {
            result.add(0);
        }
    }
    return result;
}

Count of Smaller Number II

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each elementAi in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.

Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。

建一个0-10000的值型线段树。然后每个叶子节点代表这个值的count。所以在A[i]之前比它小的数的个数就是那个0~A[i]-1这个node 的count值。之后每次Query以后把A[i]那个leaf node count++, 相应回溯更新它所有父亲节点。

时间复杂度是O(m + nlogm) m是值的区间,n是query个数。

这个算法是否最优需要分情况,如果值特别分散且query数特别小,那还不如每次query用O(n)的时间count它之前的比她小的数。

public class SegmentTreeNode {
    int start, end;
    int count;
    SegmentTreeNode left;
    SegmentTreeNode right;
    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.count = 0;
    }
}

public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
    ArrayList<Integer> result = new ArrayList<>();
    if (A == null || A.length == 0) {
        return result;
    }
    SegmentTreeNode node = buildSegmentTree(0, 10000);
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            result.add(0);
        } else {
            result.add(query(node, 0, A[i] - 1));
        }
        update(node, A[i]);
    }
    return result;
}

public SegmentTreeNode buildSegmentTree(int start, int end) {
    SegmentTreeNode node = new SegmentTreeNode(start, end);
    if (start < end) {
        int mid = start + (end - start) / 2;
        node.left = buildSegmentTree(start, mid);
        node.right = buildSegmentTree(mid + 1, end);
        node.count = node.left.count + node.right.count;
    }
    return node;
}

public int query(SegmentTreeNode node, int start, int end) {
    if (node.start == start && node.end == end) {
        return node.count;
    }
    int leftCount = 0, rightCount = 0;
    int mid = node.start + (node.end - node.start) / 2;
    if (start <= mid) {
        if (end <= mid) {
            leftCount = query(node.left, start, end);
        } else {
            leftCount = query(node.left, start, mid);
        }
    }
    if (end > mid) {
        if (start > mid) {
            rightCount = query(node.right, start, end);
        } else {
            rightCount = query(node.right, mid + 1, end);
        }
    }
    return leftCount + rightCount;
}

public void update(SegmentTreeNode node, int index) {
    if (node.start == index && node.end == index) {
        node.count = node.count + 1;
    } else {
        int mid = node.start + (node.end - node.start) / 2;
        if (node.start <= index && index <= mid) {
            update(node.left, index);
        } else if (mid < index && index <= node.end) {
            update(node.right, index);
        }
        node.count = node.left.count + node.right.count; //or node.count = node.count+1;
    }
}
FacebookTwitterGoogle+Share

Interval Sum I && II

Interval Sum I

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for each query

Solution: Version 1. prefix sum,
(Version 2. Segment tree: check Interval Sum II)

public ArrayList<Long> intervalSum(int[] A,
                                   ArrayList<Interval> queries) {
    //Version 1. prefix sum,
    //Version 2. Segment tree: check Interval Sum II
    ArrayList<Long> result = new ArrayList<>();
    if (A == null || queries == null || A.length == 0 || queries.size() == 0) {
        return result;
    }
    Long[] prefixSum = new Long[A.length];
    Long sum = 0L;
    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        prefixSum[i] = sum;
    }
    for (Interval interval : queries) {
        if (interval.start == 0) {
            result.add(prefixSum[interval.end]);
        } else {
            result.add(prefixSum[interval.end] - prefixSum[interval.start - 1]);
        }

    }
    return result;
}

Interval Sum II

Given an integer array in the construct method, implement two methods query(start, end) andmodify(index, value):

  • For query(start, end), return the sum from index start to index end in the given array.
  • For modify(index, value), modify the number in the given index to value

Example

Given array A = [1,2,7,8,5].

  • query(0, 2), return 10.
  • modify(0, 4), change A[0] from 1 to 4.
  • query(0, 1), return 6.
  • modify(2, 1), change A[2] from 7 to 1.
  • query(2, 4), return 14.

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for query and modify.

Solution: Segment Tree.

建立:O(n) 时间

查询:O(logN) 时间

更改其中一个元素: O(logN)

public class Solution {
    SegmentTreeNode root;

    public class SegmentTreeNode {
        int start, end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode right;
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public Solution(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        this.root = buildSegmentTree(A, 0, A.length - 1);
    }

    private SegmentTreeNode buildSegmentTree(int[] A, int start, int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end);
        if (start == end) {
            node.sum = A[start];
        } else {
            int mid = start + (end - start) / 2;
            node.left = buildSegmentTree(A, start, mid);
            node.right = buildSegmentTree(A, mid + 1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

    public long query(int start, int end) {
        if (start < this.root.start || end > this.root.end) {
            return -1;
        }
        return query(this.root, start, end);
    }

    private long query(SegmentTreeNode root, int start, int end) {
        if (root.start == start && root.end == end) {
            return root.sum;
        }
        int mid = root.start + (root.end - root.start) / 2;
        long leftSum = 0L, rightSum = 0L;
        if (start <= mid) {
            if (end <= mid) {
                leftSum = query(root.left, start, end);
            } else {
                leftSum = query(root.left, start, mid);
            }
        }
        if (end > mid) {
            if (start > mid) {
                rightSum = query(root.right, start, end);
            } else {
                rightSum = query(root.right, mid + 1, end);
            }
        }
        return leftSum + rightSum;
    }

    public void modify(int index, int value) {
        modify(this.root, index, value);
    }

    public void modify(SegmentTreeNode root, int index, int value) {
        if (root.start == index && root.end == index) {
            root.sum = value;
        } else {
            int mid = root.start + (root.end - root.start) / 2;
            if (index <= mid) {
                modify(root.left, index, value);
            } else {
                modify(root.right, index, value);
            }
            root.sum = root.left.sum + root.right.sum;
        }
    }
}