leetcode315:计算右侧小于当前元素的个数:三种方法的比较_右侧更小数求解

求解：右侧小于当前元素的个数三种方法
第一种:暴力解法，超时,算法复杂度为O(n^2)
第二种：使用二分查找，但是算法复杂度还是O(n^2)
第三种:可以使用bittree：树状数组进行求解，算法复杂度为O(nlgn)

package divide_and_conquer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode_315 {
	
	/**
	 * 
	 *315 计算右侧小于当前数字的个数
	 * 
	 */

	public static void main(String[] args) {
		
		
		
		int[] array = {5,2,6,1};
		List<Integer> list = new ArrayList<>();
		list = countSmaller3(array);
		for(int i : list) {
			System.out.println(i);
		}
		
	}
	
	/**
	 * 第一种最朴素的思路:最笨的方法,算法复杂度为O(n^2)
	 * 
	 * 
	 */
    public static  List<Integer> countSmaller(int[] nums) {

    	List<Integer> list = new ArrayList<Integer>();
    	
    	for(int i = 0 ; i< nums.length;i++) {
    		int number = 0;
    		for(int j = i+1;j<nums.length;j++) {
    			if(nums[i] > nums[j]) {
    				++number;
    			}
    		}
    		list.add(number);
    	}
    	
    	
		return list;
    }
    
	/**
	 * 第二种方法:可以对nums数组进行从后往前进行遍历，然后放入到arrayList中排好顺序，
	 *           当便利nums[i]的时候，可以使用二分查找得到插入的位置
	 *           
	 *           二分查找需要O(lgN),但是插入的过程复杂度为O(n)
	 *  算法复杂度：O(N^2)
	 * 
	 */
    public static List<Integer> countSmaller2(int[] nums) {

    	ArrayList<Integer> list = new ArrayList<Integer>();
    	
    	int len = nums.length;
    	Integer[] result = new Integer[len];
    	for(int i = len-1;i>=0;i--) {
    		//将每个数插入到list中//使用二分查找
    		int start = 0; int end = list.size();
    		
		    while(start<end) {
		    	int middle = start+(end-start)/2;
		    	//判断中间的数
		    	if(list.get(middle) < nums[i]) {//严格小于的话，只能在后面部分，并且不包含middle
		    		start = middle+1;
		    	}else {
		    		end = middle;
		    	}
		    }
		    result[i] = start;
		    list.add(start,nums[i]);
    	}
		return Arrays.asList(result);	
    }
    /**
     * 
     * 第三种方法：使用bitree：树状数组
     * 
     * 算法复杂度：便利一次nums为O(n)
     *			求和和更新的复杂度都为O(lgn)
     *所以整体的算法复杂度为O(nlgn)           
     *
     * 
     * 
     * 
     */
    public static  List<Integer> countSmaller3(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        int min = Integer.MAX_VALUE; // nums数组最小值
        for (int value : nums) {
            if (value < min) {
                min = value;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] - min + 1;
        }
        
        int max = Integer.MIN_VALUE;
        for (int value : nums) {
            if (value > max) {
                max = value;
            }
        }
        
        int[] BITree = new int[max + 1];
        BITree[0] = 0;
        int[] countArr = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int count = getSum(nums[i] - 1, BITree);
            countArr[i] = count;
            update(nums[i], BITree);
        }
        List<Integer> result = new ArrayList<>();
        for (int value : countArr) {
            result.add(value);
        }
        return result;
    }
    
    public static int getSum(int value, int[] BITree) { // 获得a[i]从1，value的和
        int sum = 0;
        while (value > 0) {
            sum += BITree[value];
            value -= (value & -value);
        }
        return sum;
    }

    public static void update(int value, int[] BITree) {
        while (value <= BITree.length - 1) {
            BITree[value] += 1;
            value += (value & -value);
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148