leetcode
leetcode 1901 ~ 1950
根据给定数字划分数组

根据给定数字划分数组

难度:

标签:

题目描述

代码结果

运行时间: 68 ms, 内存: 31.4 MB


/*
 * 题目思路:
 * 1. 使用Java Stream来处理数组,将元素分为小于、等于和大于pivot的三个部分。
 * 2. 将这三个部分合并成一个最终结果。
 */

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

public class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        // 使用stream过滤和收集不同条件的元素
        int[] less = Arrays.stream(nums).filter(n -> n < pivot).toArray();
        int[] equal = Arrays.stream(nums).filter(n -> n == pivot).toArray();
        int[] greater = Arrays.stream(nums).filter(n -> n > pivot).toArray();

        // 合并结果
        return Arrays.stream(new int[][]{less, equal, greater})
                .flatMapToInt(Arrays::stream)
                .toArray();
    }
}

解释

方法:

该题解使用了三个列表:less、equal 和 greater,来分别存储小于、等于和大于给定枢轴(pivot)的元素。通过遍历输入数组 nums,将每个元素分类后放入相应的列表。最后,将这三个列表依次合并,以得到符合题目要求的数组,其中小于 pivot 的元素在前,等于 pivot 的元素在中间,大于 pivot 的元素在后,同时保留了各自元素的相对顺序。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在实现pivotArray方法时,是否有考虑到nums数组为空的情况?如何处理这种情况?
在pivotArray方法的实现中,不需要特别处理nums数组为空的情况。由于三个列表(less, equal, greater)在方法开始时均被初始化为空列表,如果输入数组nums为空,遍历操作将直接跳过,最终方法返回的也将是一个空列表,即合并后的结果同样为空列表。这种处理自然地符合了对空输入数组的处理需求。
🦆
对于具有重复元素的数组,这种分类方法是否会保持重复元素的相对顺序不变?
是的,这种分类方法会保持数组中重复元素的相对顺序不变。方法通过逐个遍历数组元素并根据它们与pivot的关系加入到相应的列表中,这保证了元素在各自列表中的顺序与原数组中的顺序一致。由于最终输出数组是通过按顺序合并这三个列表生成的,因此原数组中元素的相对位置被保留。这种特性在算法中称为稳定性。
🦆
如果pivot值在数组nums中不存在,这个算法的处理方式是否有任何特殊之处?
如果pivot值在数组nums中不存在,这个算法的处理方式并无特殊之处。算法仍然会遍历整个数组,将每个元素与pivot进行比较,并按照比较结果添加到less、equal或greater列表中。由于pivot不存在于数组中,equal列表将保持为空。最终返回的数组将只包含less和greater列表的元素,按原先的顺序排列。
🦆
这种分类方法在遇到极端不均匀的数据(例如大多数元素都小于或大于pivot)时的表现如何?
在处理极端不均匀的数据时,这种分类方法的效率和空间使用将受到影响。例如,如果大多数元素都小于pivot,那么less列表将变得很大,而equal和greater列表可能非常小或为空。这种情况下,空间使用增加,因为需要额外的空间来存储每个列表中的元素。尽管如此,从时间复杂度角度来看,方法仍然是有效的,因为处理每个元素的时间是常量,整体复杂度仍为O(n)。但在最坏情况下,空间复杂度也为O(n),这可能在极端情况下导致不必要的内存使用。

相关问题