面经题排序数组平方

Easy 类似merge two sorted list, 要求O(n)

/**
  *Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array.
  *Examples:
  *Input  : arr[] =  {-6, -3, -1, 2, 4, 5}
  *Output : 1, 4, 9, 16, 25, 36 
  *Input  : arr[] = {-5, -4, -2, 0, 1}
  *Output : 0, 1, 4, 16, 25
  *   
  **/

//Time complexity: O(N)

public int[] sortSquare(int[] arr){
    int k = 0;
    int[] res = new int[arr.length];
    for (int k = 0; k < arr.length;k++){
        if (arr[k] >= 0){
            break;
        }
    }
    int i = k;//first positive element
    int j = k -1;//last negative element
    int indx = 0;
    while (j >= 0 && i < arr.length){
        if (arr[j]*arr[j] < arr[i]*arr[i]){
            res[index++] = arr[j]*arr[j];
            j--;
        } else {
            res[index++] = arr[i]*arr[i];
            i++;
        }
    }
    while (j >= 0){
        res[index++] = arr[j]*arr[j];
        j--;
    }
    while (i < arr.length){
        res[index++] = arr[i]*arr[i];
        i++;
    }
    return res;
}