s******5
发帖数: 141 | 1 这个解法有什么问题么？总是fail在最后一个test case上。test case 的input/
output很长网页上也没显示全...不知道哪儿错的。
http://www.lintcode.com/en/problem/count-of-smaller-number-befo
public class Solution {
/**
* @param A: An integer array
* @return: Count the number of element before this element 'ai' is
* smaller than it and return count number array
*/
public ArrayList countOfSmallerNumberII(int[] A) {
ArrayList list = new ArrayList<>();
int[] arr = new int[10001];
for(int i = 0; i < A.length; i++){
list.add(count(arr, 0, 10000, A[i]));
}
return list;
}
private int count(int[] arr, int i, int j, int k){
if(i==j) return 0;
int m = (i+j)/2;
if(k<=m) {
arr[m]++;
return count(arr, i, m, k);
} else {
return arr[m] + count(arr, m+1, j, k);
}
}
} |
