leetcode-977. 有序数组的平方（Stream、双指针）

男娘i 2024-03-23 12:37 76阅读 0赞

## 1、Stram流 ##

脑子里想的第一个就是Stram流  
1、将数组中的每个元素平方，返回一个新的数组（快准狠）  
2、将数组的每个元素平方，返回一个IntStream。如果原始数组是按非递减顺序排序的，则直接返回排序后的IntStream；否则对IntStream进行排序操作，最后返回排序后的数组。（针对不需要排序的情况）

/**
         * 使用Java 8中的Stream流，将数组中的每个元素平方，返回一个新的数组
         * 使用Java 8中的Stream流，将数组的每个元素平方，返回一个IntStream。
         * 如果原始数组是按非递减顺序排序的，则直接返回排序后的IntStream；否则对IntStream进行排序操作，最后返回排序后的数组。
         * <p>
         * 流是一次性的，也就是说在对流进行终止操作（如 sorted()、toArray() 等）之后，流就会被关闭，不能再次使用。
         * 如果在对流进行操作时出现 IllegalStateException: stream has already been operated upon or closed 的异常，
         * 说明该流已经被关闭了，无法再次使用。
         * <p>
         * 如果需要对一个流进行多次操作，建议将流操作结果存储在一个变量中或将流操作链拆分成多个步骤，避免重复使用流而导致异常。
         *
         * @param nums
         * @return
         */
        public static int[] sortedSquaresByStream(int[] nums) {
            // 方法一、将数组中的每个元素平方，返回一个新的数组（小数据量）
            // return Arrays.stream(nums).map(num -> num * num).sorted().toArray();
            // 方法二、将数组中的每个元素平方，再判断是否需要排序
            // 1、将数组中的每个元素平方，返回一个IntStream（将流操作结果存储在一个变量中）
            IntStream intStream = Arrays.stream(nums).map(num -> num * num);
            // 判断数组是否已经按照非降序排列，如果是则不需要进行排序(因为 nums 已按 非递减顺序 排序，如果第一个为非负数，即已排序)
            if (nums[0] < 0) {
                // 对数组进行排序操作（将流操作链拆分成多个步骤）
                intStream = intStream.sorted();
            }
    
            // 将新 IntStream 转换为 int 类型的数组（将流操作链拆分成多个步骤）
            return intStream.toArray();
    
        }

## 2、然后就是双指针yyds ##

使用双指针，通过一个索引指向新数组的最后一个元素，从数组的两端开始比较，取较大的平方值存储在新数组的末尾，直到新数组填满为止。返回新数组。

/**
         * 使用双指针，通过一个索引指向新数组的最后一个元素，从数组的两端开始比较，
         * 取较大的平方值存储在新数组的末尾，直到新数组填满为止。返回新数组。
         *
         * @param nums
         * @return
         */
        public static int[] sortedSquaresByDoublePoints(int[] nums) {
            // 新建一个数组，用于存储平方后的结果
            int[] result = new int[nums.length];
            // 定义左右指针，分别指向数组的开头和结尾
            int left = 0, right = nums.length - 1;
            // 定义一个索引，用于从数组末尾开始存储平方后的结果
            int index = nums.length - 1;
            // 当左右指针未重合时，循环进行比较和赋值操作
            while (left <= right) {
                // 如果左边的数的绝对值大于右边的数的绝对值
                if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                    // 将左边的数平方后存入结果数组
                    result[index] = nums[left] * nums[left];
                    // 左指针右移一位
                    left++;
                } else {
                    // 将右边的数平方后存入结果数组
                    result[index] = nums[right] * nums[right];
                    // 右指针左移一位
                    right--;
                }
                // 索引向前移动一位
                index--;
            }
            // 返回平方后的结果数组
            return result;
        }

## 3、直接 for 循环然后排序 ##

使用for循环遍历，计算数组中每个元素的平方，然后使用Java提供的快速排序算法（DualPivotQuicksort）进行排序。最后返回排序后的数组。

/**
         * 使用for循环遍历，计算数组中每个元素的平方，然后使用Java提供的快速排序算法（DualPivotQuicksort）进行排序。
         * 最后返回排序后的数组。
         *
         * @param nums
         * @return
         */
        public static int[] sortedSquares(int[] nums) {
            // 直接 for 循环遍历,计算数组中的每个元素平方
            for (int i = 0; i < nums.length; i++) {
                nums[i] = nums[i] * nums[i];
            }
            // DualPivotQuicksort使用两个基准值来划分数组。
            // 它先将数组分为三个部分：
            // 1、小于第一个基准值的部分、
            // 2、位于两个基准值之间的部分、
            // 3、大于第二个基准值的部分。
            // 然后对前两个部分分别递归排序，对第三个部分则继续进行划分和排序，直到所有部分都有序。
            Arrays.sort(nums);
            return nums;
        }