首页 > 数学相关 > 数论应用 > 整数集合中找出3的最大倍数-数学
2014
06-04

整数集合中找出3的最大倍数-数学

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

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

可以借助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;
}

上述方法可以优化以下方式。
1)我们可以用堆排序或归并排序,以使时间复杂度为O(nlogn)。

2)可以避免使用队列,因为只会有两个数字会被移除。

3)最后,可以不必再次排序数组,可以以相反的顺序打印升序排序的数组。

时间复杂度为O(nlogn),主要是在数组排序

参考:http://www.geeksforgeeks.org/find-the-largest-number-multiple-of-3/


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  3. 3,求得所有的为的总和sum—->所有数的总和
    printf( "Not Possible" );—->printf("impossible");
    对吗?