破解Google面试题：随机数组重排算法

"Google面试题目课程提供了一个实际问题的解决策略——如何在给定一个数组（可以理解为一副洗牌的纸牌）中的唯一整数随机重新排列，使得每种排列出现的概率相等。这个问题被称作“Deck Shuffling”或“卡牌洗牌”。理想的解法是采用被称为“希尔排序”的算法，其核心思想是遍历整个数组，每次选择一个随机元素与当前元素交换位置，但只允许交换未出现在前面位置的元素。这样做的目的是确保每个元素都有相等的机会出现在任意位置，从而实现真正的随机性。 正确答案的时间复杂度为O(n)，其中n是数组的长度。这意味着算法的运行时间随着数组大小线性增长。需要注意的是，尽管希尔排序方法是一个直观且有效的解决方案，但可能存在其他看似巧妙但实际上不正确的解答。例如，简单地对所有元素进行随机交换，而不考虑它们之前的位置，可能导致某些排列出现的概率比其他排列高，因此不满足等概率的要求。 面试官可能会考察候选人在面对此类问题时是否能够识别并选择最合适的算法，以及他们是否能够解释为什么某些看似可行的解决方案实际上是错误的。这不仅测试了编程技能，还考察了逻辑推理和问题解决的能力。在准备Google面试时，理解和掌握这类问题的解决方案将有助于提升通过面试的可能性。"