六一快乐# Joke - 肚皮舞运动
B*1
1 楼
Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
comes after a in the array.
Eg. {8,3,6,10,5}
the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
觉得这题跟amazon的这个很像,大家有没有这个感觉啊?
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create another
array ar_low[] such that ar_low[i] = number of elements lower than or equal
to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(n)
use of extra space allowed.
comes after a in the array.
Eg. {8,3,6,10,5}
the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
觉得这题跟amazon的这个很像,大家有没有这个感觉啊?
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create another
array ar_low[] such that ar_low[i] = number of elements lower than or equal
to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(n)
use of extra space allowed.