leetcode
leetcode 1351 ~ 1400
好数对的数目

好数对的数目

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 15.9 MB


/*
 * Approach:
 * We can use Java Streams to solve this problem in a more functional way.
 * We'll use a combination of IntStream and flatMap to generate all pairs of indices (i, j) where i < j.
 * Then, we'll filter these pairs to find the good pairs where nums[i] == nums[j].
 * Finally, we'll count the number of such pairs.
 */
import java.util.stream.IntStream;

public class GoodPairsStream {
    public static int numIdenticalPairs(int[] nums) {
        return (int) IntStream.range(0, nums.length)
                .flatMap(i -> IntStream.range(i + 1, nums.length)
                        .filter(j -> nums[i] == nums[j]))
                .count();
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1, 1, 3};
        System.out.println(numIdenticalPairs(nums)); // Output: 4
    }
}

解释

方法:

这个题解采用了暴力法的思路。通过两层循环遍历数组,外层循环选取基准元素,内层循环查找之后的元素中与基准元素相同的元素。每当发现相同元素时,计数器增加,最终返回计数器的值作为结果。

时间复杂度:

O(n^2)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在解决这个问题时选择使用暴力法而不是哈希表或其他更高效的数据结构?
在某些情况下,选择使用暴力法是因为其实现简单直观。尤其当数据规模较小或者对执行效率的要求不是非常严格时,暴力法可以快速实现而无需考虑额外的数据结构和复杂的逻辑。此外,初学者可能会首先考虑暴力法作为问题解决的一种基础方法,以便更好地理解问题。但对于大规模数据,哈希表等数据结构确实可以提供更优的时间复杂度。
🦆
在函数中,`ans` 是如何确保不会重复计算相同的好数对?
在这个算法中,`ans` 变量通过两层循环来确保每对好数对只被计算一次。外层循环固定一个基准元素,而内层循环从基准元素的下一个位置开始搜索,确保每次比较都是基准元素与其后面的元素进行比较。这样的循环结构保证了每个元素对只会被检查一次,从而避免了重复计数的情况。
🦆
在暴力法中,如果数组长度非常大,比如接近100,这种方法的性能表现如何?是否会有性能瓶颈?
暴力法的时间复杂度为O(n^2),其中n是数组的长度。当数组长度非常大时,比如接近100,这种方法的性能表现会显著下降。对于长度为100的数组,最坏情况下需要进行约5000次比较,这在数据量更大的情况下会导致明显的性能瓶颈,尤其是在对执行时间有严格要求的环境中。因此,对于大数据量的处理,推荐使用时间复杂度更低的算法,如使用哈希表的方法,其时间复杂度可以优化至O(n)。
🦆
在这个算法中,是否有可能通过提前终止内层循环来优化性能?
在当前的算法结构中,提前终止内层循环并不会提供性能优化,因为我们必须检查外层循环指定的每个元素后面的所有元素以寻找相同的值。由于我们的目的是找出所有可能的好数对,每一对可能的组合都需要被考虑。除非我们事先知道数组有某些特定的属性可以利用(例如有序),否则我们无法在没有检查所有可能性的情况下提前终止内层循环。

相关问题