算法题目 #
最近发现自己之前在知乎提问过一个算法问题，这个问题是10年前在我面试腾讯微信NLP组实习岗位时被问到的。
由于当时是我第一次实习面试，有点紧张，而且我当时没有问清楚，隐含条件是其实还能知道这副牌的总数，所以没有做出来。
看了下知乎的答案，没有让我特别满意的，所以时隔10年决定自己来回答这个算法题。
题目分析 #
抽象一下题目，其实就给一个数组，这个数组只有以下几个接口：
- 返回数组元素个数
- 返回数组第一个元素
- 返回数组第二个元素
- 交换数组第一个和第二个元素
- 将数组第一个元素到到数组最后
将数组排序。
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class SortDeckOfCards {
private final List<Integer> cards;
public SortDeckOfCards(List<Integer> cards) {
this.cards = cards;
}
public List<Integer> sort() {
// Implement This Function
// Only with private functions in this class
}
private int getNumberOfCards() {
return cards.size();
}
private void swapFirstTwoCards() {
Collections.swap(cards, 0, 1);
}
private void putFirstCardToEnd() {
int value = cards.remove(0);
cards.add(value);
}
private int getFirstCard() {
return cards.get(0);
}
private int getSecondCard() {
return cards.get(1);
}
}
这个算法问题其实和冒泡排序很相似，冒泡排序的思路是对于长度为n的数组，进行n次循环，第i次循环找到整个数组第i小的值，即数组index [
i - 1, n)最小的值，
然后放在数组第i个位置（冒泡🫧），每次循环后数组index [0, i)都是有序的。
假设起始数组为[1, 4，5, 2, 3]一共5个数字
【操作a】首先比较前两个数，如果第1个数小于第2个数，将前两个数对调，否则保持原顺序。 最后将第1个数的放在数组最后。（类似冒泡排序每次循环的比较)
我们重复【操作a】一共4次依次得到
[1, 5, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 3, 4, 5, 2]
[1, 4, 5, 2, 3]
因为总共5个数字，而现在第1个数字比其他4个数字都小，所以是最小的的数字。
【操作b】对调前两个数，然后把第一个数放最后
【操作c】把第一个数放最后
然后我们进行【操作c】把第1个数字放在最后得到 （类似冒泡排序的冒泡操作）
[4, 5, 2, 3, 1]
我们可以保证最后1个数字是有序的。然后我们重复【操作a】但这次只重复3次依次得到
[4, 2, 3, 1, 5]
[2, 3, 1, 5, 4]
[2, 1, 5, 4, 3]
因为现在第1个数字已经和除了最小的数字都比较了，所以是整个数组第2小的数。 而很巧的是现在第2个数就是之前最小的数。 所以我们连续进行1次【操作b】和1次【操作c】则得到
[5, 4, 3, 1, 2]
这时最后2个数字是有序的，接着我们重复【操作a】但这次只重复2次依次得到
[4, 3, 1, 2, 5]
[3, 1, 2, 5, 4]
因为现在第1个数字已经和除了最小的和第2小的数字都比较了，所以是整个数组第3小的数。 而很巧的是现在后面2个数就是之前找到的最小的和第二小的。 所以我们连续进行2次【操作b】和1次【操作c】则得到
[5, 4, 1, 2, 3]
这时最后3个数字是有序的,然后我们重复【操作a】但这次只重复1次依次得到
[4, 1, 2, 3, 5]
因为现在第1个数字已经和除了最小的，第2小的数字和第3小的数字都比较了，所以是整个数组第4小的数。 而很巧的是现在后面3个数就是之前找到的最小的，第2小的和第3小的。 所以我们连续进行3次【操作b】和1次【操作c】则得到
[5, 1, 2, 3, 4]
这时最后3个数字是有序的，第一个数字就是最小的了，然后连续进行4次【操作b】和1次【操作c】则得到有序的数组。
这其实就是这个算法的解法，如果抽象成伪代码
【操作a】首先比较前两个数，如果第1个数小于第2个数，将前两个数对调，否则保持原顺序。
【操作b】将第1个数字放在最后
function sortDeckOfCards(cards):
n = getNumberOfCards(cards)
for i from 0 to n-1:
// 执行操作a，找到第i小的数
for j from 0 to n-i-1:
if cards[0] < cards[1]:
swapFirstTwoCards(cards)
putFirstCardToEnd(cards)
// 执行操作b，将第i小的数放到最后
for k from 0 to i-1:
swapFirstTwoCards(cards)
putFirstCardToEnd(cards)
putFirstCardToEnd(cards)
return cards
算法复杂度 #
时间复杂度分析 #
- 外层循环:
- 运行 n 次，每次找到第 i 小的元素并将其移到正确位置。
- 内层第一个循环 (操作a):
- 第一次外层循环运行 n-1 次。
- 第二次外层循环运行 n-2 次。
- 依次类推，最后一次外层循环运行 1 次。
- 这部分的总操作次数是：
- \(\sum_{i=1}^{n-1} (n-i) = (n-1) + (n-2) + \ldots + 1 = \frac{(n-1)n}{2} = O(n^2)\)
- 内层第二个循环 (操作b):
- 第一次外层循环不运行（即 0 次）。
- 第二次外层循环运行 1 次。
- 依次类推，最后一次外层循环运行 n-1 次。
- 这部分的总操作次数是：
- \(\sum_{i=0}^{n-1} i = 0 + 1 + 2 + \ldots + (n-1) = \frac{(n-1)n}{2} = O(n^2)\)
综上所述，总时间复杂度为： \(O(n^2) + O(n^2) = O(n^2)\)
空间复杂度分析 #
原地排序，不需要额外的空间来存储数据。所以空间复杂度是 \(O(1)\)
算法代码 #
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class SortDeckOfCards {
private final List<Integer> cards;
public SortDeckOfCards(List<Integer> cards) {
this.cards = cards;
}
public List<Integer> sort() {
int n = getNumberOfCards();
// corner case
if (n <= 1) {
return cards;
}
// get the i-th smallest card
// after one loop, cards index [n-1-i, n-1] is sorted
for (int i = 0; i < n; i++) {
// Because cards index [n-1-(i-1), n-1] is already sorted
// so just need to get smallest in [0, n-1-i)
// eg. if total card is 3 and want to get the smallest card, just need to compare 2 times
for (int j = 0; j < n - i - 1; j++) {
int first = getFirstCard();
int second = getSecondCard();
if (first < second) {
swapFirstTwoCards();
}
putFirstCardToEnd();
System.out.println(cards);
}
// index 0 is the i-th smallest card
// index 1 to i-1 is the ordered 0 to i-1 the smallest card
// put [1, i-1]th to the end
for (int k = 0; k < i; k++) {
swapFirstTwoCards();
putFirstCardToEnd();
}
// put i-th smallest card to teh end
putFirstCardToEnd();
}
return cards;
}
private int getNumberOfCards() {
return cards.size();
}
private void swapFirstTwoCards() {
Collections.swap(cards, 0, 1);
}
private void putFirstCardToEnd() {
int value = cards.remove(0);
cards.add(value);
}
private int getFirstCard() {
return cards.get(0);
}
private int getSecondCard() {
return cards.get(1);
}
public static void main(String[] args) {
List<Integer> cards = new LinkedList<>(List.of(1, 4, 5, 2, 3));
SortDeckOfCards sortDeckOfCards = new SortDeckOfCards(cards);
System.out.println(sortDeckOfCards.sort());
cards = new LinkedList<>(List.of(5, 4, 3, 2, 1));
sortDeckOfCards = new SortDeckOfCards(cards);
System.out.println(sortDeckOfCards.sort());
cards = new LinkedList<>(List.of(6, 6, 2, 5, 7));
sortDeckOfCards = new SortDeckOfCards(cards);
System.out.println(sortDeckOfCards.sort());
}
}