977.有序数组的平方

发表于 | 分类于 ，

977. 有序数组的平方

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

示例 1：

输入：[-4,-1,0,3,10]

输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]

输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000

-10000 <= A[i] <= 10000

A 已按非递减顺序排序。

思路：其实只要做乘方之后的排序就能做出来，但是复杂度是在n^2，考虑能不能在O(n)中解出来，我的想法是，找到了数组中中间两个数的位置，也就是第一个正数和第一个负数的位置，然后通过位置的比较，来改变索引，其实我的思路是对的，用两个索引去表示位置，但是好像考虑情况比较多，数组全是正数，或者全是负数，或者正多负少，或者正少负多，最初来运行也不是很快，需要改善

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Solution_977 {
    public int[] sortedSquares(int[] A) {
        //找到两个大于等于0的第一个位置和小于等于0的位置
        int pindex = 0;
        int nindex = 0;
        int[] result = new int[A.length];
        for(int i=0;i<A.length;i++){
            if(A[i]>=0){//找到临界位置
                pindex = i;
                nindex = i-1;
                break;
            }
        }

        if(nindex==-1){
            for(int i=0;i<A.length;i++){
                result[i] = A[i] * A[i];
            }
        }else if(pindex==nindex){
            int count = 0;
            for(int i=A.length-1;i>=0;i--){
                result[count] = A[i] * A[i];
                count++;
            }
        }else {
            int count=0;
            while (true){
                //循环终止两个条件，要么pindex到末尾，要么nindex到0位
                if(nindex<0){
                    while(pindex<=A.length-1){
                        System.out.println(pindex);
                        result[count] = A[pindex]*A[pindex];
                        count++;
                        pindex++;
                    }
                    break;
                }
                if(pindex>A.length-1){
                    while(nindex>=0){
                        System.out.println(nindex);
                        result[count] = A[nindex]*A[nindex];
                        count++;
                        nindex--;
                    }
                    break;
                }

                if(-A[nindex]<A[pindex]){
                    System.out.println(nindex);
                    result[count] = A[nindex]*A[nindex];
                    count++;
                    nindex--;
                }else{
                    System.out.println(pindex);
                    result[count] = A[pindex]*A[pindex];
                    count++;
                    pindex++;
                }


            }
        }

//        for(int i=0;i<result.length;i++){
//            System.out.print(result[i]+" ");
//        }

        return result;
    }

别的思路，我看了下，其实索引位置可以定在开头和结尾，那么判断条件就是当他们两个相等时就可以终止循环了（为什么我没有想到！！！别问，问就是我菜！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] sortedSquares(int[] A) {
        int res[]=new int[A.length];
        int count=A.length-1;
        int right=A.length-1;
        int left=0;
        while(left<=right){
            if(A[left]*A[left]<=A[right]*A[right]){
                res[count]=A[right]*A[right];
                right--;
                count--;
            }else{
                res[count]=A[left]*A[left];
                left++;
                count--;
            }
        }
        return res;
    }
}

提交记录：https://leetcode-cn.com/submissions/detail/20921091/