315. Count of Smaller Numbers After Self
You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property wherecounts[i]is the number of smaller elements to the right ofnums[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.
Thoughts:
- Failed to use template for positive entry... (attaching the code)
- d
Code that I failed to implement (failed to handle properly the negative case):
class Solution {
class SegmentTreeNode{
public int start , end, cnt;
public SegmentTreeNode left, right;
public SegmentTreeNode (int start, int end, int cnt){
this.start = start;
this.end = end;
this.cnt = cnt;
this.left = this.right = null;
}
}
public List<Integer> countSmaller(int[] nums) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int num: nums){
if (num > max)
max = num;
if (num < min)
min = num;
}
// System.out.println("1: max: " + max);
SegmentTreeNode root = build(min, max);
List<Integer> ans = new ArrayList<Integer>();
int [] record = new int[nums.length];
for (int i = nums.length - 1; i >=0; i--){
// if(nums[i] > 0){
record[i] = query(root, min, nums[i] - 1);
System.out.println("i: " + i + "; nums[i]: " + nums[i] + " query: " + query(root, min, nums[i] - 1));
modify(root, nums[i], 1);
// }
}
for(int num: record){
ans.add(num);
}
// if (ans.isEmpty()){
// ans.add(0);
// return ans;
// }
return ans;
}
public SegmentTreeNode build (int start, int end){
if (start > end){
return null;
}
if(start == end){
return new SegmentTreeNode (start, end, 0);
}
int mid = (start + end) / 2;
if(mid == end){
mid -= 1;
}
System.out.println("build start: " + start + " end: " + end + " mid: " + mid);
SegmentTreeNode left = build(start, mid);
SegmentTreeNode right = build(mid + 1, end);
SegmentTreeNode ret = new SegmentTreeNode (start, end, 0);
ret.left = left;
ret.right = right;
return ret;
}
public void modify(SegmentTreeNode root, int index, int val){
if(root.start == root.end && root.end == index ){
root.cnt = val;
// System.out.println("index: " + index + " modified as: " + val);
return;
}
int mid = (root.start + root.end) /2 ;
if(mid == root.end){
mid -= 1;
}
if(root.start <= index && index <=mid){
modify(root.left, index, val);
}
if(mid < index && index <= root.end) {
modify(root.right, index, val);
}
root.cnt = root.left.cnt + root.right.cnt;
return;
}
public int query(SegmentTreeNode root, int start, int end){
if(start > end) return 0;
int mid = (root.start + root.end) / 2;
if(mid == root.end){
mid -= 1;
}
System.out.println("Query start: " + start + " end: " + end +
"; root start: " + root.start + " root end: " + root.end + " mid: " + mid
);
if (start == root.start && root.end == end){
System.out.println("exact!");
return root.cnt;
}
int ret = 0;
if (start <= mid ){
System.out.println("left!");
ret += query(root.left, start, mid);
}
if (mid + 1 <= end ){
System.out.println("right!");
ret += query(root.right, mid + 1, end);
}
return ret;
}
}
SegmentTree implementation:
class SegmentTreeNode(object):
def __init__ (self, val , start, end):
self.val = val
self.start = start
self.end = end
self.children = []
class SegmentTree(object):
def __init__ (self, n):
self.root = self.build(0, n - 1)
def build(self, start, end):
if start > end:
return
root = SegmentTreeNode(0, start, end)
if start == end:
return root
mid = start + end >> 1
root.children = filter(None, [
self.build(start, end)
for start, end in ((start, mid),(mid + 1, end))
])
return root
def update(self, i, val, root):
# root = root or self.root
if i < root.start or i > root.end:
return root.val
if i == root.start == root.end:
root.val += val
return root.val
root.val = sum([self.update(i, val, c) for c in root.children])
return root.val
def sum(self, start, end, root):
# root = root or self.root
if end < root.start or start > root.end:
return 0
if start <= root.start and end >= root.end:
return root.val
return sum([self.sum(start, end, c) for c in root.children])
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
table = {v : i for i , v in enumerate(sorted(set(nums)))}
# print(table)
tree , r = SegmentTree(len(table)), []
for i in range(len(nums) - 1, -1, -1):
r.append(tree.sum(0, table[nums[i]] - 1, tree.root))
tree.update(table[nums[i]], 1, tree.root)
return r[::-1]
BinaryIndexedTree implementation:
class BinaryIndexedTree(object):
def __init__(self, n):
self.sums = [0] * (n + 1)
def update(self, i, val):
while i < len(self.sums):
self.sums[i] += 1
i += i & -i
def sum(self, i):
r = 0
while i > 0:
r += self.sums[i]
i -= i & -i
return r
class Solution(object):
def countSmaller(self, nums):
hashTable = {v: i for i, v in enumerate(sorted(set(nums)))}
tree, r = BinaryIndexedTree(len(hashTable)), []
for i in xrange(len(nums) - 1, -1, -1):
r.append(tree.sum(hashTable[nums[i]]))
tree.update(hashTable[nums[i]] + 1, 1)
return r[::-1]
BinarySearchTree implementation:
class BSTNode(object):
def __init__ (self, val):
self.val = val
self.left = None
self.right = None
self.count = 1
self.leftTreeSum = 0
class BST(object):
def __init__ (self):
self.root = None
def insert(self, val, root):
if not root:
self.root = BSTNode(val);
return 0
if val == root.val:
root.count += 1
return root.leftTreeSum
if val < root.val:
root.leftTreeSum += 1
if not root.left:
root.left = BSTNode(val)
return 0
return self.insert(val, root.left)
if not root.right:
root.right = BSTNode (val)
return root.count + root.leftTreeSum
return root.count + root.leftTreeSum + self.insert(val, root.right)
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
tree = BST()
return [tree.insert(
nums[i], tree.root)
for i in range(len(nums) -1, -1 , -1)
][::-1]
MergeSort implementation T: O(nlogn) S: O(n)
class Solution {
protected:
void merge(vector<int>& indices, int first, int last,
vector<int>& results, vector<int>&nums){
int mid = first + (last - first)/2;
if(mid > first){
merge(indices, first, mid, results, nums);
merge(indices, mid, last, results, nums);
vector<int> sorted;
int subchild = 0;
int idx1 = first, idx2 = mid;
while((idx1 < mid) || (idx2 < last)){
if((idx2 == last) || ((idx1 < mid) &&
(nums[indices[idx1]] <= nums[indices[idx2]]) // must be <= since only counts numbers that are SMALLER
)) { //3
sorted.push_back(indices[idx1]);
results[indices[idx1]] += subchild;
idx1++;
}
else{
sorted.push_back(indices[idx2]);
subchild++;
idx2++;
}
}
move(sorted.begin(), sorted.end(), indices.begin() + first);
}
}
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> results (n, 0);
vector<int> indices (n, 0);
iota (indices.begin(), indices.end(), 0);
merge(indices, 0, n, results, nums);
return results;
}
};