Squares of a Sorted Array

1. 题目描述

一个排好序的数组，把这个数组的每个元素取平方后排序，返回排好序的数组。

2. 解法

2.1 构造数组，利用内联函数排序

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int[] ans = new int[N];
        for (int i = 0; i < N; ++i)
            ans[i] = A[i] * A[i];

        Arrays.sort(ans);
        return ans;
    }
}

2.2 利用排序特性，正数负数分别比较，降低时间复杂度。

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int j = 0;
        while (j < N && A[j] < 0)
            j++;
        int i = j-1;

        int[] ans = new int[N];
        int t = 0;

        while (i >= 0 && j < N) {
            if (A[i] * A[i] < A[j] * A[j]) {
                ans[t++] = A[i] * A[i];
                i--;
            } else {
                ans[t++] = A[j] * A[j];
                j++;
            }
        }

        while (i >= 0) {
            ans[t++] = A[i] * A[i];
            i--;
        }
        while (j < N) {
            ans[t++] = A[j] * A[j];
            j++;
        }

        return ans;
    }
}

最后顺便练习了一下快速排序，但是实际效果并没有这么好：

class Solution {
    public int[] sortedSquares(int[] A) {
        for (int i=0;i<A.length; i++){
            A[i] = (int) Math.pow(A[i],2);
        }
        QuickSort(A, 0, A.length-1);
        return A;
    }
    public void QuickSort(int[] A, int start, int end){
        if(start < end) {
            int pivot = partion(A, start, end);
            QuickSort(A, start, pivot - 1);
            QuickSort(A, pivot + 1, end);
        }
    }
    public int partion(int []Array, int low, int high){
        int pivot = Array[high];
        int i = low -1;
        int temp;
        for (int j=low; j<high; j++){
            if (Array[j] < pivot){
                i++;
                temp = Array[j];
                Array[j] = Array[i];
                Array[i] = temp;
            }
        }
        temp = Array[i];
        Array[i+1] = Array[high];
        Array[high] = temp;
        return i+1;
    }