977. 有序数组的平方

原题链接：

977. 有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

完成情况：

解题思路：

__977有序数组的平方_双指针法

    /*
    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

    请你设计时间复杂度为 O(n) 的算法解决本问题
    可以使用双指针 + 辅助空间实现
    1.就是第一次一个for循环，去找到正负边界，即知道正数有多少个，负数有多少个。
    2.然后构建一个辅助数组，在对应的边界位置创建left，right指针，去进行对新的数组的添加
     */
1
2
3
4
5
6
7
8

__977有序数组的平方_端对端大小比较

 /**
     我们可以通过端对端的大小比较，然后去对每次的结果的左右端点值去比大小，然后用left，right去指示左右对比点，同时右right又去指向我们需要对比的当前最大值的点
     如果是右边比左边大，那么正常右边向左移动
     如果左边大的话，那么就需要左边移到右边，右边的值赋到左边，然后右边--，左边++
     */
1
2
3
4
5

参考代码：

__977有序数组的平方_双指针法

package LeetCode中等题02;

public class __977有序数组的平方_双指针法 {
    /**
     * 如果我们能够找到数组 nums中负数与非负数的分界线
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        /*
        给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

        请你设计时间复杂度为 O(n) 的算法解决本问题
        可以使用双指针 + 辅助空间实现
        1.就是第一次一个for循环，去找到正负边界，即知道正数有多少个，负数有多少个。
        2.然后构建一个辅助数组，在对应的边界位置创建left，right指针，去进行对新的数组的添加
         */
        int n = nums.length;
        int negative = -1;
        for (int i = 0;i<n;i++){
            if (nums[i] < 0){
                negative = i;   //negetive即负数的最大下标位置
            }else {
                break;
            }
        }

        int [] res = new int[n];
        int index = 0,i = negative,j = negative + 1;
        while (i >= 0 || j < n){
            if (i < 0){
                res[index] = nums[j] * nums[j];
                ++j;
            } else if (j == n) {
                res[index] = nums[i] * nums[i];
                --i;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                res[index] = nums[i] * nums[i];
                --i;
            }else {
                res[index] = nums[j] * nums[j];
                ++j;
            }
            ++index;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

__977有序数组的平方_端对端大小比较

package LeetCode中等题02;

public class __977有序数组的平方_端对端大小比较 {
    /**
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        //请你设计时间复杂度为 O(n) 的算法解决本问题
        /**
         我们可以通过端对端的大小比较，然后去对每次的结果的左右端点值去比大小，然后用left，right去指示左右对比点，同时右right又去指向我们需要对比的当前最大值的点
         如果是右边比左边大，那么正常右边向左移动
         如果左边大的话，那么就需要左边移到右边，右边的值赋到左边，然后右边--，左边++
         */
        int n = nums.length;
        int res [] = new int[n];
        for (int i= 0,j = n-1,pos = n-1;i<=j;){
            if (nums[i] * nums[i] > nums[j] * nums[j] ){
                res[pos] = nums[i] * nums[i];
                ++i;
            }else{
                res[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31