360. Sort Transfromed Array

360. Sort Transfromed Array

Question

Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example:

nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]

Thinking:

• Method: Priority Queue

public class SortTransformedArray {
	public static void sort(int[] nums, int a, int b, int c){
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for(int n : nums)
			queue.add(a * n * n + b * n + c);
		int index = -1;
		while(!queue.isEmpty()){
			nums[++index] = queue.poll();
		}
	}
	public static void main(String[] args) {
		int[] nums = new int[]{-1, 2, 3,-2, 5};
		sort(nums, 1, 2, 3);
		for(int n : nums)
			System.out.println(n);
	}
}