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;
}
