FilesExpand file tree

 master

/

SortTransformedArray360.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (70 loc) · 1.96 KB

 master

/

SortTransformedArray360.java

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (70 loc) · 1.96 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

70

71

72

73

74

75

76

/**

* Given a sorted array of integers nums and integer values a, b and c. Apply

* a quadratic 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]

*/

public class SortTransformedArray360 {

public int[] sortTransformedArray(int[] nums, int a, int b, int c) {

if (nums == null || nums.length == 0) return new int[0];

int n = nums.length;

int[] res = new int[n];

int i = 0;

int j = n - 1;

int index = a >= 0 ? n - 1 : 0;

while (i <= j) {

int ii = result(nums[i], a, b, c);

int jj = result(nums[j], a, b, c);

if (a >= 0) {

if (ii >= jj) {

res[index] = ii;

i++;

} else {

res[index] = jj;

j--;

}

index--;

} else {

if (ii >= jj) {

res[index] = jj;

j--;

} else {

res[index] = ii;

i++;

}

index++;

}

}

return res;

}

private int result(int x, int a, int b, int c) {

return a * x * x + b * x + c;

}

public int[] sortTransformedArray2(int[] nums, int a, int b, int c) {

PriorityQueue<Integer> pq = new PriorityQueue<>();

for (int x: nums) {

pq.add(transfer(x, a, b, c));

}

int[] res = new int[nums.length];

int i = 0;

while (!pq.isEmpty()) {

res[i++] = pq.poll();

}

return res;

}

private int transfer(int x, int a, int b, int c) {

return a * x * x + b * x + c;

}

}