Count of Smaller Number

Question

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.

Have you met this question in a real interview? Yes 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.

• Just loop
• Sort and binary search
• Build Segment Tree and Search.

Thoughts

1.just loop

O(n^2)

1. sort and binary search

O(nlogn + logn)

1. segment tree

O(n + logn + logn)

Solution

SegmentTree

class Solution:
    """
    @param A: A list of integer
    @return: The number of element in the array that
             are smaller that the given integer
    """
    def countOfSmallerNumber(self, A, queries):
        # write your code here
        segT = SegmentTree()
        root = segT.build(0, 10000)
        for num in A:
            segT.modify(root, num, 1)

        result = []
        for q in queries:
            res = 0
            if q > 0:
                res = segT.query(root, 0, q - 1)
            result.append(res)

        return result
"""
class SegmentTreeNode:
    def __init__(self, start, end, count):
        self.start = start
        self.end = end
        self.count = count
        self.left, self.right = None, None
"""

class SegmentTree:

    def __init__(self):
        self.root = None

    def build(self, start, end):
        if start > end:
            return None
        root = SegmentTreeNode(start, end, 0)

        if start < end:
            mid = (start + end) / 2
            root.left = self.build(start, mid)
            root.right = self.build(mid+1, end)
        else:
            root.count = 0

        return root

    def query(self, root, start, end):
        if not root:
            return 0
        rStart = root.start
        rEnd = root.end

        if (rStart > end) or ( rEnd < start):
            return 0

        #should be >= and <=
        #if query range if larger than the segment tree range, just return the count
        if rStart >= start and rEnd <= end:
            return root.count

        leftCount = 0
        rightCount = 0

        mid = (rStart + rEnd) / 2
        if start <= mid:
            if end > mid:
                #some range are in right part
                leftCount = self.query(root.left, start, mid)
            else:
                leftCount = self.query(root.left, start, end)

        if mid < end:
            if start <= mid:
                #some range are in left part
                #right part should start with mid + 1
                rightCount = self.query(root.right, mid + 1, end)
            else:
                rightCount = self.query(root.right, start, end)
        return leftCount + rightCount

    def modify(self, root, index, value):
        if root.start == index and root.end == index:
            root.count += value
            return

        mid = (root.start + root.end) / 2
        if root.start <= index and index <= mid:
            self.modify(root.left, index, value)
        elif root.end >= index and index > mid:
            self.modify(root.right, index, value)

        root.count = root.left.count + root.right.count

binary search的方法

找到每个Num在数组中的index

A = sorted(A)

        results = []
        for q in queries:
            results.append(self.countSmaller(A, q))
        return results

    def countSmaller(self, A, q):
        # find the first number in A >= q
        if len(A) == 0 or A[-1] < q:
            return len(A)

        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = (start + end) / 2
            if A[mid] < q:
                start = mid
            else:
                end = mid
        if A[start] >= q:
            return start
        if A[end] >= q:
            return end
        return end + 1