数组排序余 [英] Array Sort by Remainder

问题描述

一个面试官摧残了我的生活，今天的这种问题。结果
你有一百万整数数组，你需要用剩下的对它们进行排序。结果
1.你不知道他们会被划分什么的整数。结果
2.不能使用类，如比较来帮忙。结果
3.循环尽可能少。结果
4.请记住，以节约内存。

A interviewer wrecked my life with this sort question today.
You have an array of a million integers and you need to sort them by remainder.
1. You don't know what integer they are going to divide by.
2. You can't use classes such as a Comparator to help.
3. Loop as little as possible.
4. Keep in mind to conserve memory.

例如

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次。

The method I came up with loops = divider / 2.
It works but if the divider is 250 then it loops 125 times.

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环，但其混乱阅读。结果
它违反了内存限制，但速度极快。

I wrote another method that can do it in 2 loops but its confusing to read.
It violates the memory constraint but is extremely fast.

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循环做到这一点？

How would you do this with 1 loop?

推荐答案

速度>内存

您可以循环只有使用一堆桶，每个余次。简单地倾倒在基于其剩余的桶数量，然后合并桶。当然，这违反了内存限制。

You can loop only once by using a bunch of buckets, one for each remainder. Simply dump the numbers in the buckets based on their remainder and then merge the buckets. Of course this violates the memory constraint.

使用您的数组来保存桶

与水桶的问题是，需要在阵列中的参考至少添加到每个项目。你可以做，以避免为分区数组水桶和维护每个桶的开始和结束索引的引用。当然，这使用了一些记忆，但divideBy参数应该是相当小的，对吧？

The problem with the buckets is that you need to at least add a reference to each item in the array. What you could do to avoid that is partition the array into buckets and maintain a reference to the start and end index of each bucket. Of course this uses some memory, but the divideBy parameter should be rather small, right?

所以，这里的一些伪code：

So, here's some pseudocode:

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

您注意，在最后一个我 - ，所以它在技术上可以永远继续下去。这是不是这样，我会留在地方只有当阵列[我]是不是在正确的地方。每次迭代要么放置一个元件在正确的位置或进到下一个位置，如果元素不是在正确的位置。总而言之，它会遍历最多2N次。

You will note that there is an i-- in the final for, so it technically could go on forever. That is not the case, i will stay in place only if the array[i] is not in the right place. Each iteration will either place an element in the correct position or advance to the next position if the element is not in the correct position. All in all, it will iterate at most 2N times.

总时间复杂度：O（3N + divideBy）= O（N + divideBy）

总额外的空间用于：divideBy *的sizeof（桶）= divideBy * 12

这篇关于数组排序余的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！