algorithm - 试图提高数组中此搜索的效率

Question

假设我有一个输入数组，其中所有对象都是非等价的 - 例如[13,2,36]。我希望输出数组为 [1,0,2]，因为 13 大于 2 所以“1”，2 大于没有元素所以“0”，36 大于 13 和 2 所以“2”。如何获得效率优于 O(n2) 的输出数组？编辑 1:我还想以相同的顺序打印输出。可能的话给个c/c++代码。

Answer 1

好像是动态规划。可能这可以帮助这是一个 O(n) 算法

1.声明一个最大大小为1000001的数组；

2.遍历所有元素，使arr[input[n]]=1 其中input[n]为元素

3.像这样遍历arr并与之前的索引相加(记录arr[i]大于多少个元素)

  arr[i]+=arr[i-1]

示例:如果输入[]={12,3,36}
在第 2 步之后
arr[12]=1,arr[3]=1,arr[36]=1;
第 3 步之后
arr[3]=1,arr[4]=arr[3]+arr[4]=1(arr[4]=0,arr[3]=1),
arr[11]=arr[10]=arr[9]=arr[8]=arr[7]arr[6]=arr[5]=arr[4]=1
arr[12]=arr[11]+arr[12]=2(arr[11]=1,arr[12]=1)
arr[36]=arr[35]+arr[36]=3(因为arr[13],arr[14],...arr[35]=2 and arr[36]=1)

4.遍历输入数组并打印 arr[input[i]]-1 其中 i 是索引。

所以arr[3]=1,arr[12]=2,arr[36]=3;
如果你打印 arr[input[i]] 那么输出将是 {2,1,3} 所以我们需要从每个元素中减去 1 然后输出变成 {1,0,2} 这是你想要的输出。

//伪代码

int arr[1000001];
int input[size];//size is the size of the input array
for(i=0;i<size;i++)
     input[i]=take input;//take input
     arr[input[i]]=1;//setting the index of input[i]=1; 
for(i=1;i<1000001;i++)
     arr[i]+=arr[i-1];

for(i=0;i<size;i++)
    print arr[input[i]]-1;//since arr[i] was initialized with 1 but you want the input as 0 for first element(so subtracting 1 from each element)

为了更好地理解算法，拿纸和笔做空运行。这将有助于更好地理解。

希望对你有帮助快乐编码!!