如何在O(n)时间内找出未排序数组中等于自身秩的元素？

你说得没错，完全不需要先排序数组——我们可以利用快速选择算法的变种，结合排序后数组的一个关键性质，实现平均时间复杂度O(n)的解法，比O(n lg n)的排序更高效。

核心性质分析 #

首先明确问题：我们要找是否存在元素x，使得x等于它在排序后数组中的索引i（假设索引从0开始）。由于数组元素是互不相同的整数，排序后的数组S是严格递增的，由此可以推导出一个重要性质：

序列D[i] = S[i] - i是非递减的。

因为S严格递增且是整数数组，所以S[i+1] ≥ S[i] + 1，代入得：
D[i+1] = S[i+1] - (i+1) ≥ S[i]+1 -i -1 = S[i]-i = D[i]

这意味着，如果D[k] < 0，那么所有i ≤ k的D[i]都小于0（不可能等于0）；如果D[k] > 0，所有i ≥ k的D[i]都大于0（也不可能等于0）。这个性质是我们缩小搜索范围的关键。

基于快速选择的解法思路 #

我们不需要完全排序数组，只需要每次挑选一个基准元素pivot，计算它在排序后的索引k（即数组中小于pivot的元素数量），然后通过pivot - k的结果缩小搜索范围：

• 如果pivot == k：直接找到满足条件的元素，返回true；
• 如果pivot < k：说明D[k] = pivot - k < 0，所有i ≤ k的位置都不可能满足条件，只需在大于pivot的元素子集中继续搜索；
• 如果pivot > k：说明D[k] = pivot - k > 0，所有i ≥ k的位置都不可能满足条件，只需在小于pivot的元素子集中继续搜索；

重复这个过程，直到找到目标元素或搜索范围为空（返回false）。

示例演示 #

以数组[-1, 3, 0, 2]为例：

1. 挑选pivot=3，统计小于它的元素数量k=3；
2. 比较3 == 3，直接返回true。

再以数组[2, 3, 4, 5]为例：

1. 挑选pivot=3，统计小于它的元素数量k=1；
2. 3 > 1，所以在小于3的元素子集[2]中继续搜索；
3. 挑选pivot=2，统计小于它的元素数量k=0；
4. 2 > 0，搜索范围为空，返回false。

伪代码实现 #

import random

def find_element_equal_to_rank(arr):
    def quick_select_search(sub_arr):
        if not sub_arr:
            return False
        # 随机挑选基准元素，避免最坏情况
        pivot_idx = random.randint(0, len(sub_arr)-1)
        pivot = sub_arr[pivot_idx]
        # 划分成小于pivot和大于pivot的子集
        less = [x for x in sub_arr if x < pivot]
        greater = [x for x in sub_arr if x > pivot]
        k = len(less)
        if pivot == k:
            return True
        elif pivot < k:
            # 去大于pivot的子集找
            return quick_select_search(greater)
        else:
            # 去小于pivot的子集找
            return quick_select_search(less)
    
    return quick_select_search(arr)

复杂度说明 #

• 平均时间复杂度：O(n)，每次划分后搜索范围平均缩小一半，总时间为n + n/2 + n/4 + ... = O(n)；
• 最坏时间复杂度：O(n²)（极端情况下每次划分都只缩小1个元素），但通过随机挑选基准元素可以将这种情况的概率降到极低；
• 空间复杂度：O(n)（递归和子集划分的开销），可以通过原地划分优化到O(log n)（递归栈空间）。

内容的提问来源于stack exchange，提问作者wieiooof