鱼C论坛

 找回密码
 立即注册
查看: 2383|回复: 1

[技术交流] 414_第三大的数

[复制链接]
发表于 2019-6-3 17:49:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
/*
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1
输入 [3, 2, 1]
输出 1
解释 第三大的数是 1.
示例 2
输入 [1, 2]
输出 2
解释 第三大的数不存在, 所以返回最大的数 2 .
示例 3
输入 [2, 2, 3, 1]
输出 1
解释 注意,要求返回第三大的数,是指第三大且唯一出现的数。
存在两个值为2的数,它们都排第二。
*/


解法:堆排序后再取
int     count = 0;
int*    arr   = NULL;


void _swap(int* a, int*b)
{
    int c;
    c = *a;
    *a = *b;
    *b = c;
}


void shift_up( int ind )
{
    while(  (arr[ind/2] < arr[ind])   /*大根堆:父节点的值小于新加入的孩子节点,且 ind/2 至少为1 均满足时才交换*/
          &&(ind > 1)
         )
    {
        _swap(&arr[ind/2],&arr[ind]);   /* 交换 */
         ind /= 2;                      /* 待比较对象迁移到父节点*/
    };
}

void shift_down( int ind )
{
    int moreBiggerIndex = 0;
    while(2*ind <=count) /* 有左孩子就是有孩子*/
    {
        moreBiggerIndex = 2*ind;
        if(  (moreBiggerIndex+1<=count)
           &&(arr[moreBiggerIndex+1]>arr[moreBiggerIndex])
        )
        {
            moreBiggerIndex += 1; /* 更新到右孩子*/    
        }
        if(arr[ind]<arr[moreBiggerIndex])
        {
            _swap(&arr[ind],&arr[moreBiggerIndex]);
            ind = moreBiggerIndex;
        }
        else
        {
            break;
        }
    };
}


int search_ele(int num)
{
    int ret_val = 0;
    
    for(int i = 1; i <= count ; i++)
    {
        if(arr[i] == num)
        {
            ret_val = 1;
            break;
        }
    }    
    return ret_val ;
}

void insert_ele(int num)
{
    if(search_ele(num) == 1)
    {
        return;
    }
    else
    {
        arr[count+1] = num;
        count ++;
        shift_up(count);        
    }
}

int getMax(int* ret_val) 
{
    int item;
    if(count < 1)
    {
        //cout << "此二叉堆已经为空,无法进行取出操作" << endl;
        return -1;
    }
    
    /* 获得根节点 */
    item = arr[1];
    _swap(&arr[1],&arr[count]); /*把最后一个和第一个进行交换*/
    count--;                    /* 进行计数调整*/
    shift_down(1);              /*把交换上来的数进行shift_down操作,以使堆继续满足大根堆的性质*/

    *ret_val = item;
    return 0;
}

int thirdMax(int* nums, int numsSize)
{
    int ret_val = 0;
    arr = (int*)malloc(sizeof(int)*(numsSize+1));
    if(arr == NULL)
    {
        return 0;
    }
    else
    {
        memset(arr,0,sizeof(int)*(numsSize+1));
    }
    
    for(int i = 0 ; i < numsSize ; i++)
    {
        insert_ele(nums[i]);
    }

    if (count < 3)
    {
        getMax(&ret_val);
    }
    else
    {
        for (int i = 0; i < 3; i++)
        {
            if (getMax(&ret_val) == -1)
            {
                break;
            }
        }
    }
    free(arr);
    arr = NULL;
    count = 0;
    return ret_val;
}

/*
资源和用时都爆炸了。。
执行用时 : 148 ms, 在Third Maximum Number的C提交中击败了9.00% 的用户
内存消耗 : 7.6 MB, 在Third Maximum Number的C提交中击败了6.67% 的用户
*/
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-6-3 17:51:20 | 显示全部楼层
解法2:
利用4个元素的小顶堆进行优先队列处理,降低复杂度到O(nlog4)即O(n) ,编写中。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-14 01:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表