查找标记索引的最大数量问题。

17 Mar 2025 | 4 分钟阅读

问题陈述

我们有一个 0 索引的整数数组 nums。最初，所有索引都未标记。您可以执行此操作任意次数。

选择两个不同的未标记索引 i 和 j，使得 2 * nums[i] <= nums[j]，然后标记 i 和 j。

返回使用上述操作任意次数后，nums 中可能的最大标记索引数量。

使用双指针法的 Java 代码

import java.util.Arrays;
import java.util.Scanner;
public class MaxNumOfMarkedIndices {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();
        int[] nums = new int[n]; 
        System.out.println("Enter the values for each element:");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        MaxNumOfMarkedIndicesSolution solution = new MaxNumOfMarkedIndicesSolution();
        int result = solution.maxNumOfMarkedIndices(nums); 
        System.out.println("Result: " + result);
        scanner.close();
    }
}
class MaxNumOfMarkedIndicesSolution {
    // Method to find the maximum number of marked indices
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int counter = 0;
        int i = 0, j = nums.length / 2; 
        // Compare elements and increment the counter accordingly
        while (i < nums.length / 2 && j < nums.length) {
            if (nums[i] * 2 <= nums[j]) {
                counter += 2;
                i++;
                j++;
                continue;
            }
            j++;
        }
        return counter;
    }
}

输出

Find the maximum number of marked indices problem

代码解释

该 Java 代码通过对输入数组进行排序来找到最大标记索引的数量。它初始化两个指针 i 和 j，分别遍历排序后数组的前半部分和后半部分。该算法比较这两个指针处的元素，并在满足条件 nums[i] * 2 <= nums[j] 时标记索引。
如果满足条件，计数器将增加 2，表示标记的索引。指针相应地移动，并且该过程一直持续到其中一个半部分完全遍历为止。该算法通过利用数组排序和线性遍历来有效地确定标记的索引。

时间复杂度

时间复杂度为 O(n log n)，其中 n 是输入数组的长度。由于 O(n log n) 的时间复杂度，排序过程是主要因素。

空间复杂度

空间复杂度为 O(1)。该过程，无论输入数组的大小如何，都利用固定数量的额外空间。由于排序是就地完成的，因此内存需求不会随着输入大小的增加而增加。

使用优先队列的 Java 代码

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner; 
public class MaxNumOfMarkedIndices {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();
        int[] nums = new int[n]; 
        System.out.println("Enter the values for each element:");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        MaxNumOfMarkedIndicesSolution solution = new MaxNumOfMarkedIndicesSolution();
        int result = solution.maxNumOfMarkedIndices(nums); 
        System.out.println("Result: " + result);
        scanner.close();
    }
}
class MaxNumOfMarkedIndicesSolution {
    // Method to find the maximum number of marked indices
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        int count = 0; 
        // Push elements greater than or equal to the median into the max heap
        for (int i = nums.length - 1; i >= nums.length / 2; i--) {
            queue.offer(nums[i]);
        }
        // Iterate through the first half of the sorted array
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            // If the current element is at least half of the largest remaining element
            // in the max heap, mark two indices and remove the largest element
            if (queue.size() > 0 && nums[i] * 2 <= queue.peek()) {
                count += 2;
                queue.poll();
                continue;
            }
            // Otherwise, push the current element into the max heap
            queue.offer(nums[i]);
        }
        return count;
    }
}

输出

代码解释

该 Java 代码通过对输入数组进行排序并使用优先队列来找到最大标记索引的数量。它首先按升序对数组进行排序。然后，它初始化一个最大堆（优先队列），并用大于或等于中位数的元素填充它。
该算法遍历排序数组的前半部分，通过将元素与最大堆中剩余的最大元素进行比较来标记索引。优先队列有效地维护最大元素。
该方法通过结合排序和最大堆操作来识别和标记满足指定条件的索引，从而确保正确性。

时间复杂度

排序过程主导了 O(n log n) 的时间复杂度，其中 n 是输入数组的长度。优先队列中的操作几乎没有影响。

空间复杂度

由于该算法为优先队列使用了额外的空间，因此空间复杂度为 O(n)。在最坏的情况下，优先队列的大小可能增加到 n/2，其中 n 是输入数组的长度。排序是就地完成的。

下一主题广义后缀树

查找标记索引的最大数量问题。

问题陈述

使用双指针法的 Java 代码

使用优先队列的 Java 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

查找标记索引的最大数量问题。

问题陈述

使用双指针法的 Java 代码

使用优先队列的 Java 代码

相关帖子

查找两个排序数组的相对补集

二叉树的对角线遍历

不相交集数据结构

内存高效的双向链表

数组对和可整除性问题

数据结构中的跳表

从数组中选择四条边形成的矩形的最大面积

XOR 链表 - 内存高效的双向链表

二进制转对称

数据结构中树的类型

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器