尝试改善该搜索的效率以阵列 [英] Trying to improve efficiency of this search in an array

问题描述

假设我有一个输入数组，其中所有的对象都是非等价 - 例如， [13,2,36]。我想输出数组为[1,0,2]，自13大于2，从而1，2是大于无元件以便0，36大于两个13和2，以便2。如何获取输出数组比O（n2）的效率更好？ 编辑1：我也想打印在相同的顺序输出。举一个C / C ++ code如果可能的话。

Suppose I have an input array where all objects are non-equivalent - e.g. [13,2,36]. I want the output array to be [1,0,2], since 13 is greater than 2 so "1", 2 is greater than no element so "0", 36 is greater than both 13 and 2 so "2". How do I get the output array with efficiency better than O(n2)? Edit 1 : I also want to print the output in same ordering. Give a c/c++ code if possible.

推荐答案

似乎是一个动态规划。 可能这可以帮助 下面是一个O（n）的算法

Seems like a dynamic programming. May be this can help Here is an O(n) algorithm

1.Declare数组说最大尺寸要说1000001;

2.Traverse通过所有的元素，使改编[输入[N] = 1，其中输入[n]是元素

3.Traverse经过改编，加入与previous指数（为了保持改编的纪录[我]大于多少元素）像这样

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

例：输入[] = {12,3,36}
在步骤2
改编[12] = 1，ARR [3] = 1，ARR [36] = 1;
在步骤3以后
改编[3] = 1，ARR [4] =改编[3] +改编[4] = 1（改编[4] = 0，ARR [3] = 1），
改编[11] =改编[10] =改编[9] =改编[8] =改编[7]改编[6] =改编[5] =改编[4] = 1
改编[12] =改编[11] +改编[12] = 2（改编[11] = 1，ARR [12] = 1）
改编[36] =改编[35] +改编[36] = 3（因为改编[13]，ARR [14]，...改编[35] = 2和改编[36] = 1）

Example: if input[]={12,3,36}
After step 2
arr[12]=1,arr[3]=1,arr[36]=1;
After step 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(because arr[13],arr[14],...arr[35]=2 and arr[36]=1)

4.Traverse通过输入阵列的打印改编[输入[I] - 1 其中i是该指数

4.Traverse through the input array an print arr[input[i]]-1 where i is the index.

因此​​改编[3] = 1，ARR [12] = 2，ARR [36] = 3;
如果您打印ARR [输入[I]]，然后输出为{2,1,3}，所以我们需要减去1从每一个元素，那么输出变为{1,0,2}这是你期望的输出。

So arr[3]=1,arr[12]=2,arr[36]=3;
If you print arr[input[i]] then output will be {2,1,3} so we need to subtract 1 from each element then the output becomes {1,0,2} which is your desired output.

// pseude code

//pseude code

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)

要理解算法更好，拿纸和笔做干run.It将有助于更好地理解。

To understand the algorithm better,take paper and pen and do the dry run.It will help to understand better.

希望它可以帮助 编码快乐！

Hope it helps Happy Coding!!

这篇关于尝试改善该搜索的效率以阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！