寻找数组中每个元素的下一个≥其二倍的元素，求优于O(n²)的算法

给定一个数组，对每个元素input[i]，找到其右侧第一个满足input[j] ≥ 2 * input[i]（j > i）的元素；若不存在这样的元素，输出-1。

示例：

idx:     0   1   2   3   4   5   6
Input:  23, 35, 12, 47, 33, 68, 34
Output: 47, -1, 47, -1, 68, -1, -1

说明：

• 索引3的元素47，两倍为94，右侧无元素≥94，故输出-1
• 索引4的元素33，两倍为66，右侧索引5的元素68≥66，故输出68

以下是时间复杂度优于O(n²)的两种高效解法：

解法1：分治法（O(n log²n)） #

思路 #

借鉴归并排序的分治逻辑，在合并两个有序子数组的过程中，利用右子数组的有序性，通过二分查找快速定位左子数组每个元素对应的目标值。

步骤 #

1. 递归拆分：将数组不断拆分为左右子数组，直到子数组长度为1。
2. 子问题处理：递归处理左右子数组，得到各自的结果。
3. 合并与查找：
   • 合并阶段维护右子数组的有序性；
   • 对左子数组的每个元素，在有序右子数组中二分查找第一个≥2*input[i]的元素，填入结果数组；
   • 合并左右有序子数组，为上层递归提供有序数组。

代码实现 #

def find_first_double(arr):
    n = len(arr)
    res = [-1] * n

    def divide_conquer(l, r):
        if l == r:
            return [arr[l]]
        mid = (l + r) // 2
        left_sorted = divide_conquer(l, mid)
        right_sorted = divide_conquer(mid + 1, r)

        # 处理左半部分元素的目标值查找
        for i in range(l, mid + 1):
            target = 2 * arr[i]
            low, high = 0, len(right_sorted) - 1
            ans = -1
            while low <= high:
                m = (low + high) // 2
                if right_sorted[m] >= target:
                    ans = right_sorted[m]
                    high = m - 1
                else:
                    low = m + 1
            if ans != -1:
                res[i] = ans

        # 合并有序数组
        merged = []
        p1 = p2 = 0
        while p1 < len(left_sorted) and p2 < len(right_sorted):
            if left_sorted[p1] <= right_sorted[p2]:
                merged.append(left_sorted[p1])
                p1 += 1
            else:
                merged.append(right_sorted[p2])
                p2 += 1
        merged.extend(left_sorted[p1:])
        merged.extend(right_sorted[p2:])
        return merged

    divide_conquer(0, n - 1)
    return res

# 测试
input_arr = [23, 35, 12, 47, 33, 68, 34]
print(find_first_double(input_arr))  # 输出: [47, -1, 47, -1, 68, -1, -1]

解法2：离线排序+Fenwick树（O(n log n)，最优） #

思路 #

通过离线处理将查询与候选元素统一排序，结合Fenwick树（二叉索引树）高效查询满足条件的最小右侧索引，实现线性对数级时间复杂度。

步骤 #

1. 生成条目：将每个元素拆分为「查询任务」（找j>i且arr[j]≥2*arr[i]）和「候选元素」（可能被选中的arr[j]）。
2. 排序条目：按阈值（查询任务为2*arr[i]，候选元素为arr[j]）升序排序，同阈值下候选元素优先，确保满足条件的元素先被加入数据结构。
3. Fenwick树操作：遍历排序后的条目，将候选元素索引存入树中，查询任务则在树中找大于当前索引的最小索引，对应的值即为目标元素。

代码实现 #

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [-1] * (self.n + 2)  # 存储最大的(n-j)值，对应最小的j>i

    def update(self, pos, value):
        while pos <= self.n:
            if value > self.tree[pos]:
                self.tree[pos] = value
            else:
                break
            pos += pos & -pos

    def query(self, pos):
        res = -1
        while pos > 0:
            if self.tree[pos] > res:
                res = self.tree[pos]
            pos -= pos & -pos
        return res

def find_first_double(arr):
    n = len(arr)
    res = [-1] * n
    entries = []

    # 生成查询和候选条目
    for i in range(n):
        entries.append((2 * arr[i], i, 'query'))
        entries.append((arr[i], i, 'candidate'))

    # 排序规则：先按值升序，候选条目优先于同值查询
    entries.sort(key=lambda x: (x[0], 0 if x[2] == 'candidate' else 1))

    ft = FenwickTree(n)

    for val, idx, typ in entries:
        if typ == 'candidate':
            pos = n - idx
            ft.update(pos, pos)
        else:
            max_pos = ft.query((n - idx) - 1)
            if max_pos != -1:
                j = n - max_pos
                res[idx] = arr[j]

    return res

# 测试
input_arr = [23, 35, 12, 47, 33, 68, 34]
print(find_first_double(input_arr))  # 输出: [47, -1, 47, -1, 68, -1, -1]

复杂度分析 #

• 时间复杂度：O(n log n)，排序耗时O(n log n)，每个Fenwick树操作耗时O(log n)，总共有2n个条目。
• 空间复杂度：O(n)，用于存储条目列表和Fenwick树。

内容的提问来源于stack exchange，提问作者Aayush Mohan Sinha