这里提供了一个时间复杂度为 O(n log n) 的解决方案。
正如 @SayonjiNakate 所提示的那样，使用线段树（我在我的实现中使用了 Fenwick 树）的解决方案的时间复杂度为 O(n log M)，其中 M 是数组中可能的最大值。
首先，请注意，“左侧较小元素数目”这个问题可以通过对数组进行反转和否定来等效于“右侧较大元素数目”的问题。 因此，在下面的解释中，我只描述了“左侧较小元素数目”，我称之为“lesser_left_count”。
算法 lesser_left_count：
思路是能够找到小于特定数字的总数。
定义一个大小为MAX_VALUE的数组tree，用于存储已出现过的数字值为1，否则为0。
遍历数组时，当我们看到一个数字num，只需将值1赋给tree[num]（更新操作）。此时，数字num左侧小于它的数的数量为目前为止从1到num-1的和（求和操作），因为所有比当前位置左侧更小的数字都已被设置为1。
简单吧？如果我们使用Fenwick tree，则更新和求和操作可以在O(log M)时间内完成，其中M是数组中可能的最大值。由于我们正在迭代整个数组，因此总时间复杂度为O(n log M)。
这种朴素的解决方案唯一的缺点是，随着
M变大（我在代码中设置了
M=2^20-1，大约需要4MB的内存），它使用了很多内存。可以通过将数组中的不同整数映射到较小的整数（以保留顺序的方式）来改进此问题。通过对数组进行排序，可以简单地在
O(n log n)时间内完成映射。因此，数字
M可以重新解释为“数组中不同元素的数量”。
所以内存不再是任何问题，因为如果在这种改进之后确实需要大量内存，那意味着您的数组中有
那么多不同的数字，并且
O(n)的时间复杂度已经太高无法在正常机器上计算。
为了简单起见，我没有在我的代码中包含这种改进。
哦，由于Fenwick树仅适用于正数，因此我将数组中的数字转换为最小值为1。请注意，这不会改变结果。
Python代码：
MAX_VALUE = 2**20-1
f_arr = [0]*MAX_VALUE
def reset():
global f_arr, MAX_VALUE
f_arr[:] = [0]*MAX_VALUE
def update(idx,val):
global f_arr
while idx<MAX_VALUE:
f_arr[idx]+=val
idx += (idx & -idx)
def cnt_sum(idx):
global f_arr
result = 0
while idx > 0:
result += f_arr[idx]
idx -= (idx & -idx)
return result
def count_left_less(arr):
reset()
result = [0]*len(arr)
for idx,num in enumerate(arr):
cnt_prev = cnt_sum(num-1)
if cnt_sum(num) == cnt_prev:
update(num,1)
result[idx] = cnt_prev
return result
def count_left_right(arr):
arr = [x for x in arr]
min_num = min(arr)
if min_num<=0:
arr = [min_num+1+x for x in arr]
left = count_left_less(arr)
arr.reverse()
max_num = max(arr)
arr = [max_num+1-x for x in arr]
right = count_left_less(arr)
right.reverse()
return (left, right)
def main():
arr = [1,1,3,2,4,5,6]
(left, right) = count_left_right(arr)
print 'Array: ' + str(arr)
print 'Lesser left count: ' + str(left)
print 'Greater right cnt: ' + str(right)
if __name__=='__main__':
main()
将产生：
原始数组：[1, 1, 3, 2, 4, 5, 6]
较小的左计数：[0, 0, 1, 1, 3, 4, 5]
较大的右计数：[5, 5, 3, 3, 2, 1, 0]
或者如果您想要Java代码：
import java.util.Arrays;
class Main{
static int MAX_VALUE = 1048575;
static int[] fArr = new int[MAX_VALUE];
public static void main(String[] args){
int[] arr = new int[]{1,1,3,2,4,5,6};
System.out.println("Original array: "+toString(arr));
int[][] leftRight = lesserLeftRight(arr);
System.out.println("Lesser left count: "+toString(leftRight[0]));
System.out.println("Greater right cnt: "+toString(leftRight[1]));
}
public static String toString(int[] arr){
String result = "[";
for(int num: arr){
if(result.length()!=1){
result+=", ";
}
result+=num;
}
result+="]";
return result;
}
public static void reset(){
Arrays.fill(fArr,0);
}
public static void update(int idx, int val){
while(idx < MAX_VALUE){
fArr[idx]+=val;
idx += (idx & -idx);
}
}
public static int cntSum(int idx){
int result = 0;
while(idx > 0){
result += fArr[idx];
idx -= (idx & -idx);
}
return result;
}
public static int[] lesserLeftCount(int[] arr){
reset();
int[] result = new int[arr.length];
for(int i=0; i<arr.length; i++){
result[i] = cntSum(arr[i]-1);
if(cntSum(arr[i])==result[i]) update(arr[i],1);
}
return result;
}
public static int[][] lesserLeftRight(int[] arr){
int[] left = new int[arr.length];
int min = Integer.MAX_VALUE;
for(int i=0; i<arr.length; i++){
left[i] = arr[i];
if(min>arr[i]) min=arr[i];
}
for(int i=0; i<arr.length; i++) left[i]+=min+1;
left = lesserLeftCount(left);
int[] right = new int[arr.length];
int max = Integer.MIN_VALUE;
for(int i=0; i<arr.length; i++){
right[i] = arr[arr.length-1-i];
if(max<right[i]) max=right[i];
}
for(int i=0; i<arr.length; i++) right[i] = max+1-right[i];
right = lesserLeftCount(right);
int[] rightFinal = new int[right.length];
for(int i=0; i<right.length; i++) rightFinal[i] = right[right.length-1-i];
return new int[][]{left, rightFinal};
}
}
这将产生相同的结果。
