Đề bài
Cho một mảng số nguyên nums đã được sắp xếp theo thứ tự không giảm, hãy trả về một mảng chứa bình phương của mỗi số và sắp xếp theo thứ tự không giảm.
Ví dụ 1:
Đầu vào: nums = [-4,-1,0,3,10]
Đầu ra: [0,1,9,16,100]
Giải thích: Sau khi bình phương, mảng trở thành [16,1,0,9,100]. Sau khi sắp xếp lại, mảng trở thành [0,1,9,16,100].
Ví dụ 2:
Đầu vào: nums = [-7,-3,2,3,11]
Đầu ra: [4,9,9,49,121]
Ràng buộc:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
Mảng nums đã được sắp xếp theo thứ tự không giảm.
Yêu cầu thêm:
Bình phương mỗi phần tử và sắp xếp lại mảng mới là một cách làm đơn giản, liệu bạn có thể tìm được giải pháp với độ phức tạp O(n) bằng một phương pháp khác?
Cách làm
#include <iostream>
using namespace std;
void sapXepBinhPhuong(int nums[], int n) {
int ketqua[10000]; // mang ket qua
int trai = 0, phai = n - 1;
int viTri = n - 1;
while (trai <= phai) {
int binhphai = nums[phai] * nums[phai];
int binhtrai = nums[trai] * nums[trai];
if (binhphai > binhtrai) {
ketqua[viTri] = binhphai;
phai--;
} else {
ketqua[viTri] = binhtrai;
trai++;
}
viTri--;
}
// in mang ket qua
for (int i = 0; i < n; i++) {
cout << ketqua[i] << " ";
}
cout << endl;
}
int main() {
int nums[] = {-4, -1, 0, 3, 10};
int n = sizeof(nums) / sizeof(nums[0]);
sapXepBinhPhuong(nums, n);
return 0;
}
