977. 有序数组的平方

[xiwenAndlejian]

977. 有序数组的平方

思路

从题干获取如下条件：

1. 给定的数组已按照非递减顺序排序
2. 数组非空(可以不做非空校验)，且长度小于10000(不用考虑数据溢出)
3. 数组元素范围[-10000, 10000]

需要我们返回的结果：对输入的数组元素平方，且按照非递减排序

解题

考虑条件1以及输出要求，我们的输出数组(原数组共有N个元素)：

• 第一个元素是原数组中绝对值第一小(最小)元素的平方。
• 第二个元素是原数组中绝对值第二小元素的平方。
• ...
• 最后一个元素是原数组中绝对值第N小(最大)的元素的平方。

方法一：暴力实现

因此我们可以对元素组整个进行绝对值计算(A[i] = Math.abs(A[i]))，然后再对A'数组中进行非递顺序排序。

注：A'中的符号'代表变量没有变化，但其中的值发生改变。

思路如上，实现略。

方法二：双指针

再进一步思考题干。如果建立目标输出数组和输入数组元素之间的对应关系，我们可以看出：

1. 目标数组的首个元素是从原数组的某个中点转化过来的。
2. 目标元素从左往右，对应原数组从中点往两边扩展。

如果用两个索引(li和ri)来分别表示中点左右索引，i表示目标数组(T)索引。

// 伪代码
if (abs(A[li]) > abs(A[ri])) {
    T[i] = A[ri] * A[ri];
    ri++;// 右指针往右扩展
} else {
    T[i] = A[li] * A[li];
    li++;
}

public int[] sortedSquares(int[] A) {
        int ri = findMinAbsNumIndex(A);
        int li = ri - 1;
        int i = 0;
        int[] nums = new int[A.length];
        while (i < A.length) {
            if (ri >= A.length) {
                nums[i++] = square(A[li--]);
                continue;
            }
            if (li < 0) {
                nums[i++] = square(A[ri++]);
                continue;
            }
            int left = square(A[li]), right = square(A[ri]);
            if (left < right) {
                nums[i++] = left;
                li--;
            } else {
                nums[i++] = right;
                ri++;
            }
        }
        return nums;
    }
    // 遍历数组查找第一个绝对值最小的元素索引 O(n/2)
    public int findMinAbsNumIndex(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) return i;
        }
        return nums.length;
    }

    public int square(int a) {
        return a * a;
    }
}

方法三：在方法二基础上对于某些步骤进行优化

优化查找

由于方法二中我们是迭代查找，复杂度为O(n^2/2)，属于最能优化的地方。

目标数组有序，因此可以使用二分查找，优化查找效率。根据方法二，我们需要查找的索引对应我们的右指针。

给定的数组元素有三种情况：

1. 负数和零的集合：ri = A.length - 1
2. 零和正数的集合：ri = 0
3. 正负数以及零的集合：则是我们需要通过二分查找缩小范围的情况。

思路：二分查找

1. 首先先判断当前范围的首尾元素是否符合要求：
   1. 当nums[ri] <= 0 代表符合上述情况1，返回当前右索引
   2. 当nums[li] >= 0 代表符合上述情况2，返回当前左索引
   3. 其余情况属于情况3，继续执行
2. 计算区域中点索引：mid = li + (ri - li) / 2
3. 判断nums[mid]的正负
   1. 如果等于0直接返回
   2. 负：目标索引在当前区域右半区，并且当前元素可以在下一次的查找中忽略(ri -= 1，边界缩小)。
   3. 正：目标索引在当前区域左半区，但是无法缩小右索引的边界(当前元素可能是缩小区域之后最后一个正数，因此不能忽略)。

代码

class Solution {
    public int[] sortedSquares(int[] A) {
        int mid = binarySearch(A);
        int li = mid - 1, ri = mid;
        int i = 0;
        int[] nums = new int[A.length];
        while (li >= 0 && ri < A.length) {
            int left = square(A[li]), right = square(A[ri]);
            if (left < right) {
                nums[i++] = left;
                li--;
            } else {
                nums[i++] = right;
                ri++;
            }
        }

        while (ri >= A.length && i < A.length) {
            nums[i++] = square(A[li--]);
        }
        while (li < 0 && i < A.length) {
            nums[i++] = square(A[ri++]);
        }
        return nums;
    }

    // 找到给定数组中第一个最接近非负数的索引
    // 如果数组中元素全为负，则返回最后一个元素的索引
    // 二分查找的变种
    public int binarySearch(int[] nums) {
        int li = 0, ri = nums.length - 1;
        int mid = 0;

        while (li <= ri) {
            // 排除区域中符号一致的情况
            if (nums[li] >= 0) return li;
            if (nums[ri] <= 0) return ri;
            mid = li + (ri - li) / 2;// 这样计算中点能防止大数溢出
            if (nums[mid] == 0) return mid;
            else if (nums[mid] < 0) {
                li = mid + 1;
            } else {
                ri = mid;// 需要保留此正数元素的索引，不减小范围
            }
        }
        return mid;
    }

    public int square(int a) {
        return a * a;
    }
}

:warning:由于此处将查找抽成了单个的函数，因此使用了更多的栈空间，如果想要leetcode显示双99，需要将搜索函数合并入main函数中