请教一个算法题：摇骰子， 3 个 1 和两个五一个六比， 3 个 1 获胜这种

[NicholasZhan]

楼主今天去面试了，最后的压轴题是： A 和 B 两人摇骰子，一人摇 5 次。要我找出他们俩谁赢了。获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。例如：A 出了 6 个 1，B 出了 5 个 6 和 1 个 5，则 A 获胜。楼主的思路是先统计每人每个数字出现次数，然后按照出现次数和数字本身降序排列。排序规则是这样的，出现次数多的大，次数相同则比较数字。这样就能比较出胜负了。

没想到的是，面试官突然把题目升级了：假设有 5000 个人，每个骰子有 5000 个面，每个人摇 5000 次，还是一样的规则，让我找出获胜者😢。原来的算法肯定是不行的，面试官给的提示是如何遍历一遍就给每个人打个分，然后比较分数，我只想到了权重，出现次数越多权重越大。但是具体的算法还是没能设计出来，听闻 V 站大佬多，特来请教下 ORZ 。

[cpstar]

8 进制比特位，不知道行不行，LZ 试试

[wy315700]

5000 进制

[cpstar]

5000 个面啊。。。删除我 1 楼的话

[xloger]

上班摸鱼中，没仔细看题啊，“遍历一遍就给每个人打个分”，如你所说权重，那意思是比如没重复的就是正常分数，重复一次的就是正常分数*5000，重复两次就是正常分数*5000*2 的这个思路？计算一个数，这个数是重复 N 的最小值能大于重复 N-1 的最大值的，把这个设为权重，那重复次数多分数一定高于次数低的。
好，我继续去工作了...大佬们加油！

[cpstar]

但是从取最大的算法看，确实只遍历一次足以。只不过每次遍历，需要比较的东西太多。
反正不是排序算法，不用考虑如何把 O(n^2)降到 O(nlogn)之类的

[binux]

就是取最大，最多就是自定义一个比较算法罢了。

[shpkng]

存个当前最佳结果(点数和次数)和当前最高玩家的 id,
for 5000 遍历所有玩家,
每次循环里模拟投骰子,
循环完和当前最大值比,

这样就是一次循环, 你的解法里存每个人的数据再去排序是没意义的, 直接留最大的那个就好了, 因为题目的要求只是得到一个胜者

[bfdh]

66654 和 66611 谁胜？
前者胜的话，确实遍历一次就行；后者胜的话，我再想想。

[NicholasZhan]

@bfdh 后者胜

[NicholasZhan]

规则有点像我们斗地主中的炸弹，相同的牌越多，威力越大。大的抵消了，再看第二大的炸弹，以此类推

[misdake]

先按照第一段那样统计每个人的结果，得到有序的(次数,数字)列表，把这个列表看作字符串，这个字符串就是得分，或者把他编码成一个 5000 进制的数字，每一位依次是(次数 1, 数字 1, 次数 2, 数字 2, ..., 次数 n, 数字 n, ...)。后面没有了就填 0 。
然后写一个“字符串”比较或者这个 5000 进制数字比较的函数，然后根据需求进行排序或者取最大。

[cpstar]

sum[5000][5000]=0//全都清零，第一维为人，第二维为骰子结果
maxp=0//最大的人
maxr=0//最大的骰子结果
maxs=0//最大的骰子技术
for (ppl=1..5000) {//遍历人
for (times=1..5000) {//遍历次数
sum[ppl][result]++//result 为当此骰子结果
if(sum[ppl][result]>maxs||(sum[ppl][result]=maxs&&result>maxr)) {//次数超，或者次数相等结果超
maxp=ppl;maxr=result;maxs=sum[ppl][result];
}
}
}

[cpstar]

@cpstar 12# 的方法解决不了 8#。
8#的问题已经涉及排序了。

[tyx1703]

同 2 楼，n 进制解决

6 面骰子的权重：6^0 * S_1 + 6^1 * S_2 + … + 6^5 * S_6，其中 S_n 为 出现 n 次的点数的和

66654: (6+6+6) * 6^5 + (5+4) * 6^0
66611: (6+6+6) * 6^5 + (1+1) * 6^1

[zmxnv123]

如果 A > B & B > C => A > C，我理解取最大肯定是一个 O(n)算法

[NicholasZhan]

@tyx1703 老哥你有考虑过幂运算的溢出问题吗😂

[cpstar]

@tyx1703 14# @NicholasZhan 16# 溢出还不算事，两个 6 四个 5 要赢于三个 6 三个 5 的。

另外 14#的算法写错了吧，没看懂
66654 不应该是 6*3*6^5+5*6^4+4*6^3 么
66611 不应该是 6*3*6^5+1*2*6^0 么？

如果是这样的话，
A:665555: 6*2*6^5+5*4*6^4=119232
B:666555: 6*3*6^5+5*3*6^4=159408
这就错了，

[lin07hui]

权重：5000 * (数量 - 1) * 骰子值 + 骰子值

[lin07hui]

@lin07hui 18# 权重：5000 * (数量 - 1) + 骰子值

[tyx1703]

@NicholasZhan 这只是举个计算的例子，高进制所有位的值保存在数组中，按位比较

@cpstar 写错了，应该是 (6+6+6) * 6^2 + (1+1) * 6^1

665555: 6 出现 2 次，放在第 2 位； 5 出现 4 次，放在第 4 位
5*4*6^3 + 6*2*6^1

666555: 6 出现 3 次，放在第 3 位； 5 出现 3 次，放在第 3 位
(6*3 + 5*3) * 6^2

[Encloud]

@tyx1703 每人摇 5000 次的话，极端情况就会有 5000 位的超大数

[tyx1703]

@Encloud 按位放在数组中

[wangyongbo]

leetcode 上有这道题目吗？

[NicholasZhan]

@cpstar
@wy315700
@xloger
@binux
@shpkng
@bfdh
@misdake
@tyx1703
@zmxnv123
@lin07hui
@Encloud
@tyx1703 感谢大家的热情解答，进制的解法真的很棒👍

[NicholasZhan]

@wangyongbo 貌似没有哦😂

[cctrv]

這種當然做製表啊！

把 111111 - 666666 的組合先窮盡然後按勝利到輸做一個表。

5000 人全部查表就好了。

[cctrv]

不好意思，5000 面⋯看漏了

[lin07hui]

@tyx1703
66641: (6+6+6) * 6^5 + (4+1) * 6^0
66631: (6+6+6) * 6^5 + (3+2) * 6^0
这两个相等了，应该是 66641 赢才对

[lin07hui]

@tyx1703
66641: (6+6+6) * 6^5 + (4+1) * 6^0
66632: (6+6+6) * 6^5 + (3+2) * 6^0
这两个相等了，应该是 66641 赢才对

[tyx1703]

@lin07hui 确实考虑不周，直接加还是有问题

[bdataby11]

假设有 5000 个人，每个骰子有 5000 个面（每一面的点数是 1-5000 ），每个人摇 5000 次；获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。
1.把每个人摇五千次的结果先做内部排序，统计出每个数字出现的次数，最后只要记录每个人的相同次数出现最多的数字以及其次数，5 千个人就是 5 千行结果。
2.针对次数对 5 千行结果做排序，找到次数最大的值。如果次数最大的结果有多个，再选出次数最大的

[bdataby11]

假设有 5000 个人，每个骰子有 5000 个面（每一面的点数是 1-5000 ），每个人摇 5000 次；获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。
1.把每个人摇五千次的结果先做内部排序，统计出每个数字出现的次数，最后只要记录每个人的相同次数出现最多的数字以及其次数（如第五个人 数字 1500 次数 225 ），5 千个人就是 5 千行结果。
2.针对次数对 5 千行结果做排序，找到次数最大的值。如果次数最大的结果有多个，再选出次数最大的

[bdataby11]

假设有 5000 个人，每个骰子有 5000 个面（每一面的点数是 1-5000 ），每个人摇 5000 次；获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。
1.把每个人摇五千次的结果先做内部排序，统计出每个数字出现的次数，最后只要记录每个人的相同次数出现最多的数字以及其次数（如第五个人 数字 1500 次数 225 ），5 千个人就是 5 千行结果。
2.针对次数对 5 千行结果做排序，找到次数最大的值。如果次数最大的结果有多个，再选出次数最大的


答主有些情况都没说明，每个骰子有 5000 个面，那它每一面的点数如果范围是 1-6，那是没有意义的，应该是 1-5000 比较合理。
还有个问题要考虑到，比如最终结果为[数字 1500 次数 300]的人数有两个人 a b
这时候就得取 a b 两个的 top2 做规则 [相同数字出现最多的获胜，次数相同则数字大的获胜] 比较，如果 ab 的 top2 都相等，要继续比较 top3 top4 ...topn 等等。
最最最极端的情况，5000 个人的 top1 和 topn 都相等
@NicholasZhan 大佬说的斗地主中的炸弹就差不多，我刚开始只考虑到 top1 的情况，但是如果 top1 相等的有多个，就要继续往下比较了。

[NicholasZhan]

@bdataby11 嗯，是我漏了条件，5000 面的骰子点数是 1-5000，感谢指出