算法多解 – 小米三面面试题

最近在知乎（ https://zhuanlan.zhihu.com/p/38850888 ）上看到一个小米面试题，据说是三面的题目：

一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手上没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组。

题目很简洁，不过乍看确实不太能立刻想到解题的明确步骤。不过仔细思考，其实题目也不是很复杂。这里从正、反两个角度给出不同的解。

正面角度

“取1张存1张”，说白了就是跳过一张取嘛。比如n=3时，考虑{牌1, 牌2, 牌3}，第一张取了“牌1”，那么第二张取的就是“牌3”。那只用给“牌1”标“1”、“牌3”标“2”、“牌2”标“3”就行了。换句话说，就是跳1位标数字。标过的数字就相当于桌子上的牌，没标的就相当于手上的牌。所以我们可以编写如下程序：

def card_question(n):
    result = [0] * n
    next = False
    i = 1
    while i <= n:
        for p in range(n):
            if result[p] == 0:
                if not next:
                    result[p] = i
                    i += 1
                next = not next
    return result

i就是待标记的数字，next表示是否需要跳过这位数字，由此得以实现标1位跳1位。以7位为例，算法运行过程如下图：

反面角度1

因为最后拿到手里的牌是有序的，所以直接把所有操作反过来就行了。代码是评论区 @劉長曦 编写的。

def card_question(n):
    result = []
    for i in range(n):
        result = result[-1:] + result[:-1]
        result = [(n-i)] + result
    return result

第4行是把最后一张放到牌堆最先，第5行是倒序的在首位加入牌。正好是把操作反过来执行。

反面角度2

这个角度就是“微软程序员”和轮子哥（ @vczh ）的解法，即先按照题目上的方式处理[1,n]，之后再把下标和内容交换。这也是三个解法中最抽象的一种解法了。主要的难点就是在理解交换下标与内容，那这里做一个简单的解释。

因为题中的处理本质上相当于交换元素，所以我们大可将其看作一个交换数组元素的 过程 。考虑n=5情形下处理数组A，这个过程大致有如下变换：

A[1]  =>  A[1]  A[2]  =>  A[3]  A[3]  =>  A[5]  A[4]  =>  A[4]  A[5]  =>  A[2]

题目要求给出原牌组，换句话说，就是求一个 经过上述变化能得到[1,5 ]的数组。也就是说，变换之后有：

A[1]    =>    A[1]   =  1  A[2]    =>    A[3]  =  2  A[3]    =>    A[5]  =  3  A[4]    =>    A[4]  =  4  A[5]    =>    A[2]  =  5

这样原数组就可以对应得出了：

A[1]  =  1    <=    A[1]   =  1  A[2]  =  5    <=    A[3]  =  2  A[3]  =  2    <=    A[5]  =  3  A[4]  =  4    <=    A[4]  =  4  A[5]  =  3    <=    A[2]  =  5

而我所说的这个“对应”，不就是把数组按下标{1, 3, 5, 4, 2}进行排序么？而因为数组下标本身就是有序的，所以将下标与值交换一下，就相当于进行了这样一个“排序”。回到我们的算法，我们用数组B来表示算法过程中的牌堆：

B[1]  =  1    =>    B[1]   =  1    =>    B[1]   =  1  B[2]  =  2    =>    B[2]  =  3    =>    B[2]   =  5  B[3]  =  3    =>    B[3]  =  5    =>    B[3]   =  2  B[4]  =  4    =>    B[4]  =  4    =>    B[4]   =  4  B[5]  =  5    =>    B[5]  =  2    =>    B[5]   =  3

不知道你有没有发现，后面对数组B的这一步处理和之前对数组A的处理完全相同！只不过数组A的下标就对应数组B的值，数组A的值就对应数组B的下标。所以整个算法的第一步处理，是为了获得这个处理过程对数组的处理情况，而关键的第二步，才是真正的“逆推”结果。这个算法的逆向和上个算法逆向操作不同，这个算法是在“逆推”整个处理过程。

这个算法可以如此实现：

def card_question(n):
    arr = list(range(n))
    for i in range(n-2):
        arr = arr[:i+1] + arr[i+2:]+[arr[i+1]]
    return [arr.index(x)+1 for x in range(n)]

第3-4行就是实现题中提到的处理过程的。其中第3行只处理n-2遍的原因是，最后两遍处理事实上没什么卵用（自己试试就明白了）。第5行用列表解析实现了数组下标和内容的交换。（注意下标从0开始，所以要减去1）

这个结论其实可以推广而适用于，任意一个 接受一个排列并输出这个排列的排列 的过程，证明也很容易，只需要在上述说明的基础上引入一个 记录排列后数组下标 的数组即可。这句话翻译成人话就是说，只要这个过程仅仅是改变数组的元素顺序，上面这个算法就能适用。以 将数组元素顺时针交换 这个过程为例：

def array_rotate(arr):
    return [arr[-1]]+arr[:-1]
 
def array_flip(arr):
    return [arr.index(x) for x in range(len(arr))]
 
arr = list(range(5))
arr = array_flip(array_rotate(arr))
print(array_rotate(arr))

最后输出“[0, 1, 2, 3, 4]”，与最初的arr相同。

看到这里你会发现，这个题真的不是很难。而这个题之所以被放在三面，我想更多是为了考察应试者的思维灵活性。毕竟这题不是套个模板就能过的那种算法题。撰文时我也浏览了一些博客中给出的代码，我发现现有的代码很多都有一尺多长，这其中固然有语言繁简之差，但其实这些算法大多本身就不是很简单。我相信这些算法的作者并不是想不到简洁的算法，而只是解题时陷入了思维定式。有时转变下思维，问题其实很简单。