最近发现自己很久之前在知乎提问过一个算法问题:
如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。
这个问题是 10 年前在我面试腾讯微信 NLP 组实习岗位时被问到的。由于当时是我第一次实习面试，有点紧张，而且我当时没有问清楚，隐含条件是其实还能知道这副牌的总数，所以没有做出来。当年问的知乎好像没啥答案。最近有想了一下，感觉这题其实挺有意思的，写了一个解题思路
29 条回复 • 2024-08-19 09:39:47 +08:00
 |
1
cloudzhou 31 天前
这道题目有意思，mark 一下
|
 |
2
mustcool 31 天前
有意思
|
 |
3
chen0520 31 天前
不会，等大佬。。。
|
 |
5
NoobPhper 31 天前
好像都没变过, 一直都有
|
 |
6
iOCZS 31 天前
上面冒泡总会和底部上来的有序部分相遇，这时候冒泡出来的和有序部分合并，再一起回到底部，上面继续冒泡，重复这个过程就完成排序了。
|
 |
7
InDom 31 天前
怎么感觉是冒泡啊?
|
 |
8
MoYi123 31 天前
|
 |
9
newtype0092 31 天前
暂时想不到其他的办法，看起来就是冒泡。。。
对扑克牌这种数据连续的场景，因为当前要找的第 i 小的牌是已知的，如果遇到了可以直接 break ，算是个微微优化吧，对时间复杂度没影响就是了。 |
 |
10
sillydaddy 31 天前 via Android
想了半分钟。这不就是冒泡吗？最上面的 2 张牌就是冒泡算法里面对比大小并交换的 2 张牌。将最上面一张放到底部，就是 index+1 ，比较下 2 张牌。
|
 |
11
forty 31 天前
人脑怎么排，写成代码就能实现了，优化是另一层的问题。跟冒泡很像啊。
先不考虑优化，一种很简单的策略来实现： 1. 比较上面 2 张，将大的放到底部去，再比较上面 2 张，又将大的放到底部去，这样重复一轮之后，最小的那张就在最上面了，此时把这个最小的放到底下去。 2. 重复步骤 1 ，找到第二小的了，且此时最小的这 2 张是相邻的，2 张都放到底下去（先小后大）。 3. 一直重复就可以了， 直到最上面变成最小的那张。 逻辑很简单吧。 |
 |
12
sobev 31 天前
比较的时候只需要把小牌的留在最前面就好了，大的直接往后放，等一轮循环结束，最小的牌就在最前面。
下次循环 index+1 |
 |
13
q727729853 31 天前
@forty 你重复步骤 1 的时候，最小的两张就不可能相连了。。你已经放了个大的到底部了。。。
|
 |
14
hackhu2019 31 天前
基于选择排序，我们每次取两张牌，把最小的牌留着，大的牌放排底，重复一轮，最小的牌就在最上面了，再从第二张牌开始重复这个过程
|
 |
15
kkbear 31 天前
@hackhu2019 问题是，第二轮开始，你并不能锁定第一轮最小的牌让其不移动
|
 |
17
wineast 31 天前
@kkbear 在第二轮开始前，把第一轮找到的最小牌放到最下面，这样，第二轮结束的时候（这一轮 每次比较都会有一张牌被放到最下面，使得第一轮的那张最小牌被“冒泡”上来），应该是 第二小牌，第一小牌，其他牌 这个顺序
|
 |
18
vgbhfive 31 天前
@hackhu2019 第一轮排序完后，最小的牌在最前面，在开始第二轮之前，把最小的牌挪到最后面，然后再继续比较第一张和第二张，此时第二张的取值范围就是[0, n-2]。
|
 |
19
dinghmcn 31 天前
@q727729853 #13 第二轮完成，上面两张就是最小的两张，因为你要把 N-2 放到下面会把最小的顶上来；第 N 轮完成前 N 张就是最小的 N 张；逻辑没有问题，本质就是冒泡。
|
|
20
iOCZS 31 天前
一叠纸牌从上到下分为冒泡区，有序区，无序区。冒泡区保证最小的在在顶部，冒泡区淘汰的进入无序区，最终冒泡区的大小会变为 1 ，和有序区相遇，并融入其中。这时候再把有序区整体搬到底部。就变成新的冒泡区，有序区，空的无序区。
|
 |
21
fayeeeeee 31 天前  1
这个是不是厄斐琉斯的控刀啊
|
 |
22
leonshaw 31 天前 via Android
反过来把牌堆看作不动，等价于在每次数组中读取指针当前和下一个元素，选择对调与否，然后指针后移（尾部折返）。
|
 |
23
vance123 31 天前 via iPhone
归纳法吗
|
 |
24
iEverX 31 天前
|
 |
25
iwdmb 30 天前
 惊讶 ChatGPT 的实力... |
 |
27
milkpuff 29 天前
 写了一个好像可以实现 |
|
28
forty 29 天前
@q727729853 “@forty 你重复步骤 1 的时候，最小的两张就不可能相连了。。你已经放了个大的到底部了。。。”
并不会。 我再解释一下吧。 假设 54 张牌，目标是排成这样的顺序：黑桃 A, 黑桃 2, 黑桃 3…… 第 1 轮，达成牌堆：******,黑桃 A 。 第 2 轮，先达成牌堆：黑桃 2******黑桃 A******。不停，保持黑桃 2 在最上，把其它牌换到底下去。直到黑桃 2 下面就是黑桃 A ，最小的 2 张就相邻了。再做 3 步操作，达成牌堆：******,黑桃 A,黑桃 2 。 第 3 轮，达成牌堆：******,黑桃 A, 黑桃 2, 黑桃 3 。 以此类推。 这样能理解吗？ |
 |
29
smdbh 28 天前
不是大的放上面，然后在放最底下。 如果 n 次不交换，排序完成？
|
Select Language