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