有序数组的平方 的排序（力扣.977）

有序数组的平方 的排序（力扣.977） 题目：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求新数组 也按 非递减顺序 排序。 1.直接排序

将数组 nums 中的数平方，然后排序。因为使用了排序算法, 时间和空间复杂度都很高。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }
}

2.双指针思想 2.1、方法一：

数组原本是有序的, 只是在平方之后就变得无序了, 根本原因就是数组中的负数 平方之后可能成为最大数了, 那么数组元素 平方后的最大值就在数组的两端, 不是最左边就是最右边, 不可能是中间。

要确定数组中元素平方后的最大值的位置。可以用双指针指向数组的两端, 必定能找到平方后的最大值, 将其放到新数组末尾, 之后两个指针不断向中间移动。通过比较两个指针平方后的大小, 就能不断地将当前的最大值放入数组的尾部, 直到两个指针相遇为止。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] res = new int[nums.length];
        int index = res.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[index--] = nums[left] * nums[left];
                ++left;
            } else {
                res[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return res;
    }
}

2.2、方法二：

另外一种稍微麻烦一点的方式就是 先找到数组中 负值和正值的分界点, 相当于找到了平方后的最小值, 然后向两边不断进行遍历。这种方法多了一层循环来找分界点。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n=nums.length;
        int negative=-1;
        for(int i=0;i=0||j 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5694586.html