obsidian/АиСД/Задачи/LeetCode/Squares of a Sorted Array.md

Leetcode #977 | #Easy | Два указателя | Указатель на запись

Идея

Два указателя - один с конца другой с начала (идея в том что большие квадраты по краям). Дальше бежим по циклу указателем write с конца и заполняем с конца, то есть большими числами (сравниваем их по абсолютной величине)

Big-O

• Время O(N)
• Память O(N)

Код

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int l = 0, r = n - 1;
        for (int w = n - 1; w >= 0; w--) {
            if (Math.abs(nums[l]) > Math.abs(nums[r])) { res[w] = nums[l] * nums[l]; l++; }
            else { res[w] = nums[r] * nums[r]; r--; }
        }
        return res;
    }
}