Better way to minimize array elements

Question

I would like the array elements to minimize by preserving their orders. For example:

• 3,7,9,7 is given 1,2,3,2 is yielded
• 1,99,90,95,99 is given 1,4,2,3,4 is yielded.

Think array can be ranged btw 0 to 100, exclusively. My try’s time complexity is \$O(n^3 + n)\$.

Can there be more efficient way to solve this?

int[] arr = new int[] {2,5,3,5}; // example input


var copy = (int[])arr.Clone();
var num = 101;
foreach(var x in arr)
{
    var min = copy.Min();
    for(int i = 0 ; i < arr.Length; i++)
    if(min == arr[i])
    {
        copy[i] = num;
    }
    num++;
}

for (int i = 0; i < copy.Length; i++)
{
    copy[i] = copy[i] % 100;
}

Answer 1

Indents

I've spent a minute struggling to understand that copy[i] = num; happens inside the second for loop. Please, indent the code to make it readable - you will gain from it in the first place.

Your algorithm is \$O(n^2)\$

First, \$O(n^3+n) = O(n^3)\$. \$O(n)\$ can be neglected because it is small compared to \$O(n^3)\$. Second, I don't see any third loop inside the second.

Better algo

1. Sort the copy of the array, \$O(n*log(n))\$.
2. Make some search structure to convert a number in a sorted array into its index (map or another array), \$O(n)\$.
3. Change all numbers in the first array to their indexes in sorted array, \$O(n)\$.

Answer 2

This is zero based index and the example is one based index, can add one if need to match. I didn't do timing test to see if this is faster or even look at memory consumptions. To me this reads and makes it easier to maintain. I prefer maintenance over performance unless it's needs to be performance skewed for the area of code it's in.

SortedList takes two values but we don't care about the value so just toss in a bool to make it happy. Then using the IndexOfKey method that uses a binary search. Which under the covers uses Array.BinarySearch. Could take SortedList out of the picture and use Array.BinarySearch to do similar to what SortListed is doing if having the bool value that isn't used is a deal breaker for you.

public static int[] Positions(params int[] items)
{
    var sortedList = new SortedList<int, bool>(items.Length);
    for (var i = 0; i < items.Length; i++)
    {
        sortedList.TryAdd(items[i], false);
    }

    var result = new int[items.Length];
    for (var i = 0; i< items.Length; i++)
    {
        result[i] = sortedList.IndexOfKey(items[i]);
    }

    return result;
}

EDIT: If you want to avoid SortedList you can do what it's doing pretty simple.

public static IEnumerable<int> Position(params int[] items)
{
    var distinct = new HashSet<int>(items);
    var clone = new int[distinct.Count];
    distinct.CopyTo(clone);
    Array.Sort(clone);
    for (var i = 0; i < items.Length; i++)
    {
        yield return Array.BinarySearch(clone, items[i]) + 1;
    }
}

Answer 3

Can there be more efficient way to [canonicalise values between minV and maxV in an array preserving rank]?

Yes. Let me suggest another mechanism in-stead of sorting / ordering (the latter being what most procedures with a name derived from sort do):
When the range of values maxV - minV is small, use an array about that size to

1. find which values do appear
   (When keeping count of value frequencies, this can be used for ordering using value counts: counting sort.)
2. assign canonical values
3. map input values to canonical values

Answer 4

You can improve the complexity to O(N.Log(N)) (on average) at the expense of space by introducing an adjunct array containing the numbers 0..N-1 and sorting it at the same time as the original array.

This will yield a set of indices that you can use to populate a results array like so:

int[] arr = { 1, 99, 90, 95, 99 };
int[] tmp = Enumerable.Range(0, arr.Length).ToArray();
int[] res = new int[arr.Length];

Array.Sort(arr, tmp);
int ind = 0;

for (int i = 0; i < arr.Length; ++i)
{
    if (i == 0 || arr[i] != arr[i-1])
        ++ind;

    res[tmp[i]] = ind;
}

Console.WriteLine(string.Join(", ", res));  // 1, 4, 2, 3, 4