Bình phương mảng đã sắp xếp trong C++

Cho một mảng số nguyên đã sắp xếp tăng dần, nhiệm vụ là tính bình phương mỗi phần tử và trả về mảng kết quả cũng theo thứ tự tăng dần. Ví dụ:

Đầu vào 1:

arr[] = {-3, -1, 0, 1, 4, 6}

Đầu ra:

{0, 1, 1, 9, 16, 36}

Giải thích: Bình phương các phần tử: 9, 1, 0, 1, 16, 36. Sau khi sắp xếp: 0, 1, 1, 9, 16, 36.

Đầu vào 2:

arr[] = {0, 1, 2, 8, 9}

Đầu ra:

{0, 1, 4, 64, 81}

Phương pháp giải quyết

Sử dụng kỹ thuật Two Pointers (Hai con trỏ). Vì mảng đã sắp xếp, các số âm (nếu có) ở đầu, số dương ở cuối. Bình phương của số âm lớn có thể lớn hơn bình phương số dương nhỏ. Ta dùng hai con trỏ left (đầu) và right (cuối), so sánh bình phương, lấy giá trị lớn hơn đưa vào kết quả (từ cuối về đầu), sau đó đảo ngược mảng kết quả.

• Khởi tạo left = 0, right = n-1.
• Khi left <= right: tính v1 = arr[left]^2, v2 = arr[right]^2.
• Nếu v1 > v2, đẩy v1 vào kết quả, tăng left; ngược lại đẩy v2, giảm right.
• Cuối cùng đảo ngược mảng kết quả để có thứ tự tăng dần.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

vector<int> squareAndSort(vector<int> &arr) {
    int left = 0, right = arr.size() - 1;
    vector<int> res;
    while (left <= right) {
        int v1 = arr[left] * arr[left];
        int v2 = arr[right] * arr[right];
        if (v1 > v2) {
            res.push_back(v1);
            left++;
        } else {
            res.push_back(v2);
            right--;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    vector<int> arr = {-3, -1, 0, 1, 4, 6};
    vector<int> ans = squareAndSort(arr);
    for (int x : ans) cout << x << ' ';
    return 0;
}

Kết quả

0 1 1 9 16 36

Phương pháp chạy trong O(n) thời gian và O(n) không gian phụ.