Java 中查找标记索引的最大数量

问题陈述

给定一个 数组 nums。问题是找到最大的索引集，使得对于每个选定的索引 i，都存在另一个选定的索引 j，满足 A[i] ≤ 2 × A[j]。任务是找出最大可能的标记索引数。

示例 1

输入: nums = {3, 5, 2, 8, 10}

输出: 最大标记索引数: 4

解释: 排序后: {2, 3, 5, 8, 10}。有效对是 (2,8) 和 (3,10)，因此标记了 4 个索引。

示例 2

输入: nums = {10, 20, 30, 40, 50, 60}

输出: 最大标记索引数: 6

解释: 排序后的数组: {10, 20, 30, 40, 50, 60}。有效对是 (10,30)、(20,40) 和 (30,60)，标记了所有 6 个索引。

排序和双指针方法

该方法使用排序和双指针技术来查找给定数组中最大标记索引数。

算法

步骤 1: 将数组按升序排序。

步骤 2: 初始化两个指针

1. left 从开头开始（较小的元素）。
2. Right 从中间开始（较大的元素）。

步骤 3: 尝试通过检查 nums[left] * 2 <= nums[right] 来形成有效对

1. 如果有效，则计数增加 2，left 向前移动。
2. 始终将 right 向前移动。

步骤 4: 重复此过程，直到其中一个指针耗尽。

步骤 5: 返回标记索引的总数。

让我们在 Java 程序中实现上述方法。

输出

 
Maximum Marked Indices: 4   

时间复杂度: 程序的 O(n log n)，其中 n 是数组的大小。这是因为排序和数组的遍历。

空间复杂度: 程序的 O(1)。这是因为原地排序，没有使用额外空间。

二分查找结合贪心方法

该方法用于查找最大标记索引数。其思想是搜索满足条件 A[i] ≤ 2 × A[j] 的最大对数。

算法

步骤 1: 对数组进行排序，以确保元素按非递减顺序排列。

步骤 2: 对可能的标记对数 (mid) 使用二分查找。

步骤 3: 在 canMark() 中检查是否可以用贪心策略标记 mid 对

1. 比较最小对的元素与最大对的元素。
2. 如果所有对都满足 A[i] × 2 ≤ A[j]，则有效。

步骤 4: 如果可以标记 mid 对，则搜索更多对 (left = mid + 1)；否则，减小搜索空间 (right = mid - 1)。

步骤 5: 返回 maxMarked，它存储找到的最大有效索引。

让我们在 Java 程序中实现上述方法。

输出

 
Maximum Marked Indices: 4   

时间复杂度: 程序的 O(n log n)，其中 n 是数组的大小。这是因为排序和二分查找。

空间复杂度: 程序的 O(1)。这是因为我们对数组进行原地修改，并且不使用额外空间。