Recover Count Array | tech::interview
本题跟另外一个G家的面试题也异曲同工:
给一个数组a[n],
令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)
Read full article from Recover Count Array | tech::interview
给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数组。实际上就是求O(logn)的第k小的元素。问题可以转化为带count数的BST或者线段树。
原数组中元素是一个[1,n]的随机排列。
For example:
Count array:[3, 0, 1, 0]
Original array:[4, 1, 3, 2]
Can you give an O(nlogn) solution?
本题跟另外一个G家的面试题也异曲同工:
给一个数组a[n],
令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)
Read full article from Recover Count Array | tech::interview