LintCode:统计比给定整数小的数的个数
尝试用线段树,超时。
public class Solution { /** * @param A: An integer array * @return: The number of element in the array that * are smaller that the given integer */ int res; public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) { // write your code here ArrayList<Integer> ans = new ArrayList<Integer> (); for(int i=0; i < queries.length; i++){ ans.add(0); } if(A.length == 0){ return ans; } int n = A.length - 1; int root_val = max(A, 0, n); SegmentTreeNode root = new SegmentTreeNode(0, n, root_val); buildSegmentTree(root, A); int m = 0; for(int query: queries){ res = 0; myQuery(root, query); ans.set(m++, res); } return ans; } public void buildSegmentTree(SegmentTreeNode root, int[] A){ if(root.start == root.end){ return; } int left_start = root.start; int left_end = (root.start + root.end) / 2; int left_val = max(A, left_start, left_end); int right_start = (root.start + root.end) / 2 + 1; int right_end = root.end; int right_val = max(A, right_start, right_end); root.left = new SegmentTreeNode(left_start, left_end, left_val); root.right = new SegmentTreeNode(right_start, right_end, right_val); buildSegmentTree(root.left, A); buildSegmentTree(root.right, A); } public int max(int[] A, int start, int end){ int maxNum = A[start]; for(int i=start; i<=end; i++){ if(A[i] > maxNum){ maxNum = A[i]; } } return maxNum; } public void myQuery(SegmentTreeNode root, int num){ if(root == null){ return; } if(root.max < num){ res += root.end - root.start + 1; return; } myQuery(root.left, num); myQuery(root.right, num); } }那就用二分法吧
public class Solution { /** * @param A: An integer array * @return: The number of element in the array that * are smaller that the given integer */ public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) { // write your code here ArrayList<Integer> ans = new ArrayList<Integer> (); for(int i=0; i < queries.length; i++){ ans.add(0); } if(A.length == 0){ return ans; } quickSort(A, 0, A.length-1); int m = 0; for(int query:queries){ int res = myQuery(A, query); ans.set(m++, res); } return ans; } public void quickSort(int[] A, int m, int n){ if(m >= n){ return; } int i = m; int j = n; int tmp = A[i]; while (i < j){ while(i < j && A[j] >= tmp){ j --; } A[i] = A[j]; while(i < j && A[i] <= tmp){ i ++; } A[j] = A[i]; } A[i] = tmp; quickSort(A, m, i-1); quickSort(A, i+1, n); } public int myQuery(int[] A, int query){ int high = A.length - 1; while(A[high] >= query && high > 0){ high /= 2; } while(A[high] < query && high < A.length - 1){ high += 1; } return high; } }