找出3的最大倍数的整数集合

灰太狼 2022-09-25 11:15 106阅读 0赞

**题目描述**：给一个包含非负整数的数组(长度为n)，找出由这些数字组成的最大的3的倍数，没有的话则输出impossible。例如，如果输入的数组为\{8,1,9\}，输出应为“9 8 1”，并且如果输入的数组为\{8,1,7,6,0\}，输出应为”8760″。

**方法一 :暴力**  
直接用蛮力的话，生成所有的组合，为 2n个，对每个数字再进行比较判断，需要 O(n)的时间，因为n可能会比较大，需要每个位的比较。  
总的时间复杂度为O(n∗2n).

方法二:数学技巧  
可以借助O(n)的额外空间有效的解决这个问题。该方法是基于对数以下的简单性质：

*  1）一个数是3的倍数，则该数字各位总和为3的倍数。例如，让我们考虑8760，它是3的倍数，因为数字总和为8 + 7 + 6 + 0 = 21，这是3的倍数。
 *  2）如果一个数是3的倍数，那么它的所有排列也为3的倍数，例如，6078是3的倍数，数字8760，7608，7068，…也为3的倍数。
 *  3）一个数的所有位之和与该数会有相同的余数。例如，如果对于151和它的各位之和7，对于3的余数都为1。

我们可以用下面的算法：

*  1.对数组进行非递减排序。
 *  2.用3个队列 queue0,queue1,queue2，分别存储除以3余数为 0、1、2的数字。
 *  3.求得所有的为的总和sum
 *  4.有下面三种情况：  
    
    
     *  a) sum除以3余0。出列的所有三个队列中的数字，以非递减顺序排序输出到结果数组中。
     *  b) sum除以3余1。则尝试从queue1中移除一个元素或从queue2中移除两个元素，如果不可以的话，则说明impossible
     *  c) sum除以3余2。则尝试从queue1中移除两个元素或从queue2中移除一个元素，如果不可以的话，则说明impossible
 *  5.最后将3个队列中的所有元素都输出到结果数组中，非递减排序，即为最终结果。

下面是C语言实现代码：

#include <stdio.h>
    #include <stdlib.h>
    
    // 自定义队列节点
    typedef struct Queue
    {
        int front;
        int rear;
        int capacity;
        int* array;
    } Queue;
    
    //创建一个队列
    Queue* createQueue( int capacity )
    {
        Queue* queue = (Queue *) malloc (sizeof(Queue));
        queue->capacity = capacity;
        queue->front = queue->rear = -1;
        queue->array = (int *) malloc (queue->capacity * sizeof(int));
        return queue;
    }
    
    // 检测队列是否为空
    int isEmpty (Queue* queue)
    {
        return queue->front == -1;
    }
    
    //想队列添加一个元素
    void Enqueue (Queue* queue, int item)
    {
        queue->array[ ++queue->rear ] = item;
        if ( isEmpty(queue) )
            ++queue->front;
    }
    
    // 从队列删除一个元素
    int Dequeue (Queue* queue)
    {
        int item = queue->array[ queue->front ];
        if( queue->front == queue->rear )
            queue->front = queue->rear = -1;
        else
            queue->front++;
    
        return item;
    }
    
    // 打印数组
    void printArr (int* arr, int size)
    {
        int i;
        for (i = 0; i< size; ++i)
            printf ("%d ", arr[i]);
    }
    
    int compareAsc( const void* a, const void* b )
    {
        return *(int*)a > *(int*)b;
    }
    int compareDesc( const void* a, const void* b )
    {
        return *(int*)a < *(int*)b;
    }
    
    // 将3个队列中的元素输出到辅助数组
    void populateAux (int* aux, Queue* queue0, Queue* queue1,
                                Queue* queue2, int* top )
    {
        while ( !isEmpty(queue0) )
            aux[ (*top)++ ] = Dequeue( queue0 );
    
        while ( !isEmpty(queue1) )
            aux[ (*top)++ ] = Dequeue( queue1 );
    
        while ( !isEmpty(queue2) )
            aux[ (*top)++ ] = Dequeue( queue2 );
    }
    
    int findMaxMultupleOf3( int* arr, int size )
    {
        // 第1步，排序
        qsort( arr, size, sizeof( int ), compareAsc );
    
        Queue* queue0 = createQueue( size );
        Queue* queue1 = createQueue( size );
        Queue* queue2 = createQueue( size );
    
        // 第2,3步
        int i, sum;
        for ( i = 0, sum = 0; i < size; ++i )
        {
            sum += arr[i];
            if ( (arr[i] % 3) == 0 )
                Enqueue( queue0, arr[i] );
            else if ( (arr[i] % 3) == 1 )
                Enqueue( queue1, arr[i] );
            else
                Enqueue( queue2, arr[i] );
        }
    
        //第四部，b)
        if ( (sum % 3) == 1 )
        {
            if ( !isEmpty( queue1 ) )
                Dequeue( queue1 );
            else
            {
                if ( !isEmpty( queue2 ) )
                    Dequeue( queue2 );
                else
                    return 0;
                if ( !isEmpty( queue2 ) )
                    Dequeue( queue2 );
                else
                    return 0;
            }
        }
    
        // 第4步，c)
        else if ((sum % 3) == 2)
        {
            if ( !isEmpty( queue2 ) )
                Dequeue( queue2 );
            else
            {
                if ( !isEmpty( queue1 ) )
                    Dequeue( queue1 );
                else
                    return 0;
                if ( !isEmpty( queue1 ) )
                    Dequeue( queue1 );
                else
                    return 0;
            }
        }
    
        int aux[size], top = 0;
    
        // 第5步
        populateAux (aux, queue0, queue1, queue2, &top);
        qsort (aux, top, sizeof( int ), compareDesc);
    
        // 打印结果
        printArr (aux, top);
    
        return 1;
    }
    
    // 测试
    int main()
    {
        int arr[] = {
       8, 1, 7, 6, 0};
        int size = sizeof(arr)/sizeof(arr[0]);
    
        if (findMaxMultupleOf3( arr, size ) == 0)
            printf( "Not Possible" );
    
        return 0;
    }

关于 [程序算法艺术与实践][Link 1]更多讨论与交流，敬请关注本博客和新浪微博songzi\_tea.

[Link 1]: http://blog.csdn.net/column/details/tac-programalgrithm.html