Array Сортировать по Остальное

Question

Интервьюер разрушил мою жизнь таким вопросом сегодня.
У вас есть массив из миллиона целых чисел, и вам нужно отсортировать их по остатку.
1. Вы не знаете, какое целое число они делят на.
2. Вы не можете использовать классы, такие как Comparator, чтобы помочь.
3. Петли как можно меньше.
4. Имейте в виду сохранение памяти.

Например

int[] ints = {5434, 3454, 2, 0, 356, 896, 7324, 888, 99, 78365, 111}; 
int divider = 27; 

Был бы

int[] int2 = {0, 2, 111, 356, 896, 5434, 7324, 78365, 99, 888, 3454}; 

Метод, который я придумал петли = делитель/2.
Это работает, но если делитель равен 250, то это петли 125 раз.

public void sortByMod(int[] millionInts, int divideBy) { 
    long time = System.nanoTime(); 
    int[] b = new int[millionInts.length]; 
    int remainder, remainderMin = 0, remainderMax = divideBy, positionMin = 0, positionMax = millionInts.length - 1; 
    for (int i = 0; i < millionInts.length;) { 
     for (int j = 0; j < millionInts.length; j++) { 
      remainder = millionInts[j] % divideBy; 
      if (remainder == remainderMin) { 
       b[positionMin] = millionInts[j]; 
       positionMin++; 
       i++; 
      } else if (remainder == remainderMax) { 
       b[positionMax] = millionInts[j]; 
       positionMax--; 
       i++; 
      } 
     } 
     remainderMax--; 
     remainderMin++; 
    } 
    System.out.println("time = " + (System.nanoTime() - time)); 
    System.out.println("loopcount = " + remainderMin); 
} 

Я написал другой метод, который может сделать это в 2 циклах, но смущает его читать.
Он нарушает ограничение памяти, но очень быстро.

public void sortByModPro(int[] millionInts, int divideBy) { 
    int[] range = new int[divideBy]; 
    int[] remainders = new int[millionInts.length]; 
    int[] newArray = new int[millionInts.length]; 
    long times = System.nanoTime(); 
    for (int i = 0; i < millionInts.length; i++) { 
     remainders[i] = millionInts[i] % divideBy; 
     range[millionInts[i] % divideBy]++; 
    } 
    for (int i = range.length - 1, past = millionInts.length; i >= 0; i--) { 
     range[i] = past - range[i]; 
     past = range[i]; 
    } 
    for (int i = 0; i < millionInts.length; i++) { 
     newArray[range[remainders[i]]] = millionInts[i]; 
     range[remainders[i]]++; 
    } 
    System.out.println("time = " + (System.nanoTime() - times)); 
} 

Как вы это сделаете с помощью 1 петли?

Answer 1

Скорость> Память

Вы можете цикл только один раз, используя кучу ведер, по одному для каждого остатка. Просто выкиньте числа в ведрах на основе их остатка, а затем объедините ведра. Конечно, это нарушает ограничение памяти.

Используйте массив для хранения ведер

Проблема с ведрами является то, что вам нужно, по крайней мере, добавить ссылку к каждому элементу в массиве. Что бы вы могли сделать, чтобы избежать этого, разделите массив на ведра и сохраните ссылку на индекс начала и конца каждого ведра. Конечно, это использует некоторую память, но параметр divideBy должен быть довольно небольшим, не так ли?

Итак, вот некоторые псевдокод:

// init each bucket with 0 elements 
for (remainder=0; remainder<divideBy; remainder++) { 
    buckets = { 
    start : 0, // startIndex in the array 
    end: 0, // the index after the last item actually placed in the bucket 
    count: 0 // how many items should be in the bucket 
    } 
} 
// count how many elements fit in each bucket 
for (i=0; i<N; i++) { 
    buckets[array[i]%divideBy].count++; 
} 
// init the start and end points of each bucket 
elementsCounted=0; 
for (remainder=0; remainder<divideBy; remainder++) { 
    buckets[remainder].start = elementsCounted; 
    buckets[remainder].end = elementsCounted; 
    elementsCounted += buckets[remainder].count; 
} 

// at this point each bucket starts where it should in the array, but has no elements 

// loop through the array and place items in the right bucket by swapping them 
for (i=0; i<N; i++) { 
    remainder = array[i]%divideBy; 
    if (i < buckets[remainder].start || i >= buckets[remainder].end) { 
    // array[i] is in the wrong bucket, swap it at the end of the right bucket 
    swap(array[i], array[buckets[remainder].end]); 
    buckets[remainder].end++; 
    i--; 
    } 
} 

// everything is in the right place 

Вы заметите, что есть i-- в финале за, так что технически может продолжаться вечно. Это не так, я останусь на месте, только если массив [i] находится не в нужном месте. Каждая итерация либо помещает элемент в правильное положение, либо переходит в следующую позицию, если элемент не находится в правильном положении. В целом, он будет выполнять итерацию не более 2 раз.

Общее время сложность: O (3n + DIVIDEBY) = O (N + DIVIDEBY)

Общее дополнительное пространство используется: DIVIDEBY * SizeOf (ведро) = DIVIDEBY * 12