CodingQuestion/src/LeetCode-977-Squares-of-a-Sorted-Array.java at master · drinkbeer/CodingQuestion · GitHub

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

class Solution {
    // 1. Binary Search + Two Pointers
    /*
    Binary Search: O(logN)
    Scan: O(N)

    Overall Time: O(N)

    */
//     public int[] sortedSquares(int[] nums) {

//         int l = binarySearch(nums), r = l + 1;

//         int[] res = new int[nums.length];
//         int cnt = 0;
//         while (l >= 0 || r <= nums.length - 1) {
//             int lv = Integer.MAX_VALUE, lr = Integer.MAX_VALUE;
//             if (l >= 0) {
//                 lv = nums[l] * nums[l];
//             }

//             if (r <= nums.length - 1) {
//                 lr = nums[r] * nums[r];
//             }

//             if (lv < lr) {
//                 res[cnt++] = lv;
//                 l--;
//             } else {
//                 res[cnt++] = lr;
//                 r++;
//             }
//         }

//         return res;
//     }

//     // search the right most idx, has nums[idx] < 0
//     private int binarySearch(int[] nums) {
//         int lo = 0, hi = nums.length - 1;
//         while (lo + 1 < hi) {
//             int mid = lo + (hi - lo) / 2;
//             if (nums[mid] >= 0) {
//                 hi = mid;
//             } else {
//                 lo = mid;
//             }
//         }

//         if (nums[hi] < 0) return hi;
//         return lo;
//     }

    // 2. Two Pointers
    /*
    Scan from two edges to middle.
    Time O(N)
    */
    public int[] sortedSquares(int[] nums) {
        int lo = 0, hi = nums.length - 1;

        int[] res = new int[nums.length];
        int cnt = nums.length - 1;
        while (lo <= hi) {
            if (Math.abs(nums[lo]) < Math.abs(nums[hi])) {
                res[cnt--] = nums[hi] * nums[hi];
                hi--;
            } else {
                res[cnt--] = nums[lo] * nums[lo];
                lo++;
            }
        }
        return res;
    }
}