leetcode
leetcode 2101 ~ 2150
与对应负数同时存在的最大正整数

与对应负数同时存在的最大正整数

难度:

标签:

题目描述

代码结果

运行时间: 32 ms, 内存: 16.2 MB


/*
 * 思路:
 * 我们可以利用 Java Stream 的特性来简化代码。
 * 首先将数组转换为一个 Set 集合,
 * 然后利用 Stream 过滤出所有满足条件的正整数,
 * 最后返回最大值。
 */

import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution {
    public int findMaxK(int[] nums) {
        Set<Integer> numSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        return Arrays.stream(nums)
                     .filter(num -> num > 0 && numSet.contains(-num))
                     .max()
                     .orElse(-1);
    }
}

解释

方法:

解法首先创建了一个集合来存储数组中的所有元素,这有助于快速判断一个元素是否存在于数组中。然后,对数组进行从大到小的排序,这样可以优先检查较大的正整数。对于每一个正整数,检查其对应的负数是否也在集合中。一旦找到这样的正整数,立即返回它,因为它是满足条件的最大正整数。如果遍历结束也没有找到,则返回 -1。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在解题中需要将数组转化为集合?集合与数组在查找效率上有什么区别?
在解题中将数组转化为集合的主要原因是为了提高查找效率。数组的查找操作通常需要遍历整个数组来找到一个元素,这在最坏的情况下是线性时间复杂度,即O(n)。而集合(特别是哈希集合)通常提供更快的查找时间,平均情况下可以达到常数时间复杂度,即O(1)。这种时间复杂度的差异使得集合在需要频繁查找操作的场景下比数组更加高效。
🦆
解法中提到对数组进行降序排序后遍历,为什么选择降序而不是升序排序?
解法中选择对数组进行降序排序的原因是为了尽快找到满足条件的最大正整数。通过降序排序,数组中较大的数会排在前面,这样在遍历时可以优先检查这些较大的数。一旦遍历到第一个同时存在其对应负数的正整数,就可以直接返回这个数,因为它肯定是所有满足条件的正整数中最大的。如果使用升序排序,则需要遍历整个数组才能确定是否有满足条件的最大正整数。
🦆
在解法中,如果数组中有多个相同的正整数k及其对应的负数-k,这种情况会影响算法的输出吗?
如果数组中有多个相同的正整数k及其对应的负数-k,这种情况不会影响算法的输出。算法的目标是找到最大的正整数k,使得k和-k都存在于数组中。无论这个k出现了多少次,只要它存在并且它的对应负数-k也存在,就满足条件。算法在找到第一个这样的k时就会停止搜索并返回该数,因此多个相同的k及其负数的存在不会改变结果。
🦆
考虑到Python的set是无序的,直接迭代set而不是排序后的数组会怎样影响算法的结果和性能?
如果直接迭代Python的无序set而不是排序后的数组,将不能保证遍历的顺序,从而可能会错过最大的满足条件的正整数k。在性能方面,虽然遍历set可能稍微快一些,因为不需要排序操作,但这种方法不能保证找到最大的k,可能需要额外的逻辑来跟踪遇到的最大满足条件的正整数。因此,排序后的数组遍历方法在保证找到正确结果的同时,牺牲了一些性能。

相关问题