首页 > 试题广场 >

有一堆扑克牌,其中某张牌的张数超过了扑克牌总数的一半,请找到

[问答题]
有一堆扑克牌,其中某张牌的张数超过了扑克牌总数的一半,请找到这张牌。写出算法思路、代码实现和算法的时间复杂度,要求算法尽可能高效。假设给定一个扑克牌的数组poker和它的大小n,请返回所求的扑克牌。
思路:扑克牌的数组poker中一张牌出现的次数超过了数组长度的一半,即这个牌出现的次数比其他所有牌的出现次数和还要多。可考虑:遍历数组的时候保存两个值:一是数组中的牌,另一是次数。当我们遍历到下一个数字时,如果与保存数字相同,次数+1;不同,-1、 若次数=0,则保存下一数字,并设次数为1. 因为,要找的数字出现的次数比其他所有的数字出现的次数之和还要多,那么要找的数字肯定是最后一次把次数设置1时对应的牌。

int num=poker[0];
int cnt=1;
for(int i=1;i<n;i++){
    if(poker[i]==num)
        cnt++;
    else
        cnt--;
    if(cnt==0){
        num=poker[i];
        cbt=1;
}
}
return num;

时间复杂度 O(n)
发表于 2018-04-13 20:32:44 回复(1)
对扑克牌数组进行排序,定义一个临时变量来存放当前张数最多的扑克牌,定义两个计数器来计数按顺序的排放的相邻两中牌的数量,将数量多的存放在临时变量中,一次进行搜索,则可以得到所要求的扑克牌。
发表于 2018-04-12 21:07:15 回复(0)
这里比剑指offer里面的《超过一半数》少了个判断是否超过一半,因为题目明确指出了,“存在”大于一半的,所以不需要加判断。
发表于 2018-03-26 16:45:52 回复(0)
这个题目的思路应该和在数组中寻找出现次数超过一半的题目类似
int num = poker[0];
int cnt = 1;
for (int i = 1; i < n; i++)
{
    if (poker[i] == num) cnt++;
    else cnt--;
    if (cnt == 0)
    {
         num = poker[i];
         cnt = 1;
    }
}
return num;
因为出现次数大于一半 所以num最后一定是那个数。
O(n) 复杂度。
发表于 2018-03-25 20:01:24 回复(0)
很经典的问题超过半数问题
	
for(int i = 1; i <= n; i++){
    if(num == 0){
         now = a[i];
         num = 1;
          continue;
    }
    if(a[i]!=now)
        num--;
    else num++;
}
printf("%d\n",now);
因为超过一半,每每两个不同的牌配合出局,那么最后留下来的一定是超过一半的那个牌,时间复杂度为O(n)

发表于 2018-03-24 16:15:46 回复(0)