c - 从 O(n) 时间复杂度的数字数组中找到 3 的最大倍数

Question

给定一个数字数组(0 到 9)。求数组的部分或全部数字能组成的最大能被3整除的数。同一个元素在数组中可以出现多次，但数组中的每个元素只能使用一次。
例子:
输入:arr[] = {5, 4, 3, 1, 1}
输出:4311
算法

获取数组大小和数组输入并在获取输入时计算总和。

按升序对数组进行排序

取三个队列，迭代数组并除以3并根据余数放入各自的队列，Queue0保存数字%3 == 0Queue1保存数字%3 == 1Queue2保存数字%3 == 2

计算余数 = sum % 3，如果余数等于 1，则从 Queue1 中取出一个元素或从 Queue2 中取出两个元素；如果剩余数等于 2，则从 Queue2 中取出一个元素或从 Queue1 中取出两个元素

将 Queue0、Queue1 和 Queue2 合并为一个队列

按降序对合并队列进行排序

打印合并队列。

代码

#include<stdio.h> 
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    int a[n],q1[n],q2[n],q3[n];
    int c1=0,c2=0,c3=0;
    for(int i=0;i<n;i++) {
    scanf("%d",&a[i]);
    sum+=a[i]; }
    for(int i=0;i<n;i++){
        if(a[i]%3==0) {
            q1[c1]=a[i]; c1++; }
        else if(a[i]%3==1) {
            q2[c2]=a[i]; c2++; }
        else {
            q3[c3]=a[i]; c3++; }
    }
    if(sum%3==1&&c1!=0)
    c1--;
    else {
        if(c2>1)
            c2-2;
        else
            printf("Not Possible");
    }
    if(sum%3==2&&c2!=0)
    c2--;
    else {
        if(q1>1)
            c1-2;
        else
            printf("Not Possible");
    }
    int k=0,b[n];
    for(int i=0;i<c1;i++) {
        b[k]=q1[i]; k++; }
    for(int i=0;i<c2;i++) {
        b[k]=q2[i]; k++; }
    for(int i=0;i<c3;i++) {
        b[k]=q3[i]; k++; }
    }

我是编码新手，无法弄清楚 O(n) 中的排序和合并队列。在第 2 步和第 5 步中需要帮助。

Answer 1

排序 O(n) ，你会想要使用 Radix sort .

// Let's start with the array that your code generates in step 5
int b[4] = {1, 1, 4, 3}

// Count the number of times each value is seen.
int buckets[10] = {};
for (int i=0; i<4; i++)
  buckets[b[i]]++;

// Update the b array with the sorted data.
int *b_iterator = &b[0];
for (int i=0; i<10; i++)
  for (int count=0; count<buckets[i]; count++)
    *b_iterator++ = i;

// b is now sorted. {1, 1, 3, 4}.