时间戳

首页 > 解决方案 > 程序按余数排序数组 3

c - 程序按余数排序数组 3

问题描述

我被要求编写一个运行时间为 n 的高效函数，该函数按 3 的余数对数组进行排序，程序将除以 3 的余数为 0 的元素放在余数为 1 的元素之后为 2，例如数组 { 7, 16, 3, 28, 12, 31, 14, 12} 将以 {12, 3, 12, 28, 16, 31, 7, 14} 的方式排序，所以我尝试编写一个有效的函数，但它没有涵盖所有情况，不适用于所有数组

    int arr[] = { 7,16,3,28,12,31,14,12 };
    int rem0 = 0, rem1 = 1, rem2 = 2;

    for (int i = 0; i < 8; i++) {
        if (arr[i] % 3 == 0)
            rem0++;

        if (arr[i] % 3 == 1)
            rem1++;

        if (arr[i] % 3 == 2)
            rem2++;
    }

    int k = rem0, p = 0, m = 0 = 0;

    for (int i = 0; i < 8; i++) {
        while (rem0-k){
            swap(&arr[i], &arr[rem0 - k]);
            k--;
        }
        if (arr[i] % 3 == 1 && rem0+m<7) {
            swap(&arr[i], &arr[rem0 + m]);
            m++;
        }
        if (arr[i] % 3 == 1 && rem0 + rem1 + p<7) {
            swap(&arr[i], &arr[rem0+rem1 + p]);
            p++;
        }
    }

    for (int l = 0;l <8;l++) {
        printf("%d\n", arr[l]);
    }
}

void swap(int *a, int *b) 
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

交换开关元件，谁能告诉我如何解决这个问题？

谢谢：）

标签： carrays

解决方案

由于您希望函数在 O(n) 时间内运行，因此您无法对数组进行完全排序。您需要做的就是将所有元素放入 3 个桶中。以下算法分两个阶段运行。

//First we count the number of elements in each bucket 
int count[3] ={0, 0, 0};
for (int i = 0; i < NUM_ELEMENTS; i++) {
    count[arr[i]%3]++;
}

现在我们有了元素的数量，我们可以计算每个桶的偏移量并创建和输出数组

int output[NUM_ELEMENTS]; // In place bucketing can also be done using swaps
count[2] = count[0] + count[1];
count[1] = count[0];
count[0] = 0;


for (int i = 0; i < NUM_ELEMENTS; i++) {
    output[count[arr[i]%3]] = arr[i];
    count[arr[i]%3]++;
}

// Finally print the array

for (int i = 0; i < NUM_ELEMENTS; i++) {
    printf("%d", output[i]);
}

Ideone上的演示

推荐阅读