按剩余的4对数组进行排序

Question

我有一个练习,我必须按以下方式对数组进行排序:

1. 除以4而没有余数的数字将是数组中的第一个(例如4,8,12,16).
2. 将剩余的1除以4的数字将是数组中的第二个(1,5,9).
3. 将剩余的2除以4的数字将是数组中的第三个(2,6,10).
4. 将剩下的3除以4的数字将在数组中最后.

例如,以下数组:

int []a={1,7,3,2,4,1,8,14}

将会:

4   8   1   1   2   14  3   7   

组内的顺序无关紧要.

我找到了一个解决O(n)时间复杂度和O(1)空间复杂度的解决方案.

然而,它是丑陋的,并在阵列上移动3次.我想要一个更优雅的解决方案.

这是我的代码:

    int ptr=a.length-1; int temp=0, i=0;
    while (i<ptr){
        //move 3 remained to the end
        if (a[i] % 4==3){
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==2)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==1)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }

重要的是要知道:

• 我不希望时间复杂度比O(n)差,并且空间复杂度比O(1)差.

Answer 1

由于O(3*N)是O(N),你只需要遍历数组三次:

1. 将元素e % 4 == 0移到前面,沿途交换元素;
2. 将元素e % 4 == 1移到前面,沿途交换元素;
3. 将元素e % 4 == 2移到前面,沿途交换元素;

e % 4 == 3在此之后将会结束的元素.

例:

public static void main(String args[]) {
    int[] a = { 1, 7, 3, 2, 4, 1, 8, 14 , 9};
    int current = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = current; j < a.length; j++) {
            if (a[j] % 4 == i) {
                int b = a[j];
                a[j] = a[current];
                a[current] = b;
                current++;
            }
        }
    }
    System.out.println(Arrays.toString(a));
}