力扣 977. 有序数组的平方_力扣有序数组的平方c语言

1 力扣题目来源

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

https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

2 思路分析

2.1 双指针法

数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

考虑双指针法，left 指向起始位置，right 指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[left] * A[left] < A[right] * A[right] 
	那么result[k--] = A[right] * A[right]; 
如果A[left] * A[left] >= A[right] * A[right] 
	那么result[k--] = A[left] * A[left]; 
1
2
3
4

图片来源 代码随想录

3 代码实现

public class 有序数组的平方 {
    public static void main(String[] args) {
        System.out.println("===开始测试数组中元素的平方===");
        int[] arr = {-5, -3, 3, 2};

        int[] rsArr = sortedSquares(arr);

        for (int i = 0; i < rsArr.length; i++) {
            System.out.println("新数组的元素为：" + rsArr[i]);
        }
    }

    /**
     * @param arr 每个元素待平方的数组
     * @return 排好序的每个元素平方后的结果
     */
    public static int[] sortedSquares(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        int k = arr.length - 1;
        int[] newArr = new int[arr.length];
        while (left <= right) {
            if (arr[left] * arr[left] < arr[right] * arr[right]) {
                newArr[k] = arr[right] * arr[right];
                right--;
                k--;
            } else {
                newArr[k] = arr[left] * arr[left];
                left++;
                k--;
            }
        }
        return newArr;
    }
}

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