Trying to improve efficiency of this search in an array

Question

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.

Answer 1

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

1.Declare an array of say max size say 1000001;

2.Traverse through all the elements and make arr[input[n]]=1 where input[n] is the element

3.Traverse through the arr and add with the previous index(To keep record of arr[i] is greater than how many elements) like this

  arr[i]+=arr[i-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 through the input array an print arr[input[i]]-1 where i is the index.

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

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)

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!!

Answer 2

Clone original array (and keep original indexes of elements somewhere) and quicksort it. Value of the element in quicksorted array should be quicksorted.length - i, where i is index of element in the new quicksorted array.

[13, 2, 36] - original
[36(2), 13(1), 2(0)] - sorted
[1, 0, 2] - substituted

Answer 3

def sort(array):
    temp = sorted(array)
    indexDict = {temp[i]: i for i in xrange(len(temp))}
    return [indexDict[i] for i in array]

I realize it's in python, but nevertheless should still help you

Answer 4

Schwartzian transform: decorate, sort, undecorate.

Create a structure holding an object as well as an index. Create a new list of these structures from your list. Sort by the objects as planned. Create a list of the indices from the sorted list.