Trong mảng các số nguyên được sắp xếp đã cho, nhiệm vụ là in các ô vuông của mọi phần tử mảng và in mảng theo thứ tự đã sắp xếp. 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ủa mỗi phần tử của mảng [-3, -1,0,1,4,6] đã cho là [0,1,1,9,16,36].
Đầu vào-2 -
arr[ ]= { 0,1,2,8,9 } Đầu ra -
{0,1,4,64,81} Giải thích - Bình phương của mỗi phần tử của mảng [0,1,2,8,9] đã cho là [0,1,4,64,81].
Phương pháp tiếp cận để giải quyết vấn đề này
Để giải quyết vấn đề cụ thể này, chúng ta có thể sử dụng phương pháp Hai con trỏ. Trong Two-Pointer, chúng tôi sử dụng hai con trỏ trái và phải. Con trỏ bên trái được khởi tạo với phần tử đầu tiên của mảng và con trỏ bên phải trỏ đến phần tử kết thúc của mảng.
Trong khi lặp qua các phần tử của mảng, chúng ta sẽ tìm bình phương của giá trị và kiểm tra xem bình phương của số nguyên bên phải lớn hơn hay nhỏ hơn số nguyên bên trái.
-
Nhập một mảng các số nguyên theo thứ tự tăng dần.
-
Một hàm số nguyên squareAndSort (int * arr, int n) nhận đầu vào là một mảng các số nguyên và trả về bình phương của mỗi phần tử trong mảng theo cách được sắp xếp.
-
Khởi tạo hai con trỏ trái và phải với phần tử bên trái và phần tử ngoài cùng bên phải của mảng.
-
In bình phương của phần tử và so sánh với bình phương của phần tử bên phải.
-
Tăng và giảm con trỏ trái và phải cho phù hợp.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
vector<int> squareAndSort(vector<int>&arr){
int left= 0;
int right= arr.size()-1;
vector<int>vec;
while(left<=right){
while(left <= right) {
int v1 = arr[left]*arr[left];
int v2 = arr[right]*arr[right];
if(v1 <= v2) {
vec.push_back(v2);
right--;
}
else {
vec.push_back(v1);
left++;
}
}
reverse(vec.begin(), vec.end());
}
return vec;
}
int main(){
vector<int>arr= {-3,-1,0,1,4,6};
vector<int>ans= squareAndSort(arr);
for(auto x:ans){
cout<<x<<" ";
}
return 0;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
0 1 1 9 16 36
Bình phương của mỗi phần tử của mảng là, 9,1,0,1,16,36. Sau khi sắp xếp các phần tử này, kết quả đầu ra sẽ là 0 1 1 9 16 36.