Clever Geek Handbook

Attempting to improve the efficiency of this array search

Suppose I have an input array where all objects are not equivalent - eg. [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 13 and 2 so "2" ... How to get the output array with better efficiency than O (n2)? Edit 1: I also want to print the output in the same order. Specify c / C ++ code if needed.

+3


source to share


4 answers


Similar to dynamic programming. Maybe it can help Here is an O (n) algorithm

1. Define an array with a maximum size of 1000001;

2. Step over all elements and make arr [input [n]] = 1, where input [n] is an element

3. Step through arr and add with the previous index (To keep the record arr [i] greater than the number of 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 (since arr [13], arr [14], ... arr [35] = 2 and arr [36] = 1)



4. Step through the print input array arr[input[i]]-1

, where i is the index.

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

// alias 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 better understand the algorithm, take a paper and pen and do a dry run. This will help you better understand.

Hope this helps Happy Coding!

0


source


Clone the original array (and store the original element indices somewhere) and sort it quickly. The value of the element in the quicksorted array must be quicksorted.length - i

, where i

is the index of the element in the new quicksorted array.



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


source 


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

I understand this in python but should help you nonetheless

0


source


Schwarz transform: decorate, sort, decompose.

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

0


source






More articles:


All Articles