🌕 977. 有序数组的平方

难度: 🌕

• 问题描述
• 解法 1 - 双指针 + 二分找最小值
• 输出 1
• 解法 2 - 双指针
• 输出

问题描述

---

解法 1 - 双指针 + 二分找最小值

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 思路：
        // 找到平方最接近 0 的数
        // 双指针往两边扩散
        int len = nums.length;
        int[] res = new int[len];
        int index = 0;
        if(nums[0] * nums[len - 1] < 0) {
            // 二分查找 - 找到最接近 0 的负数下标
            int left = mySol(nums, 0, len - 1);
            int right = left + 1;
            while(left >= 0 && right < len) {
                if(Math.abs(nums[left]) < nums[right]) {
                    res[index] = (int)Math.pow(nums[left], 2);
                    index ++;
                    left --; 
                } else {
                    res[index] = (int)Math.pow(nums[right], 2);
                    right ++;
                    index ++;
                }
            }
            while(left >= 0) {
                res[index] = (int)Math.pow(nums[left], 2);
                index ++;
                left --;
            }
            while(right < len) {
                res[index] = (int)Math.pow(nums[right], 2);
                index ++;
                right ++;
            }
        } else if(nums[0] >= 0) {
            // 最小值 >= 0
            for(int i = 0; i < len; i ++) {
                res[index] = (int)Math.pow(nums[i], 2);
                index ++;
            }
        } else {
            for(int i = len - 1; i >= 0; i --) {
                res[index] = (int)Math.pow(nums[i], 2);
                index ++;
            }
        }
        return res;
    }

    private int mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return left;
        }
        if(nums[right] < 0) {
            return right;
        }
        // left < right
        int mid = left + ((right - left) >> 1) + 1;
        if(nums[mid] > 0) {
            right = mid - 1;
            return mySol(nums, left, right);
        } else if(nums[mid] < 0) {
            left = mid;
            return mySol(nums, left, right);
        } else {
            return mid;
        }
    }
}

---

输出 1

---

解法 2 - 双指针

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 思路：
        // 双指针，从两侧边界值往中心推进
        int len = nums.length;
        int[] res = new int[len];
        int index = len - 1;
        int left = 0;
        int right = len - 1;
        while(left <= right) {
            int aa = nums[left] * nums[left];
            int bb = nums[right] * nums[right];
            if(aa >= bb) {
                left ++;
                res[index] = aa;
                index --;
            } else {
                right --;
                res[index] = bb;
                index --;
            }
        } 
        return res;
    }
}

---

输出