ในอาร์เรย์ของจำนวนเต็มที่เรียงลำดับแล้ว งานคือพิมพ์กำลังสองของทุกองค์ประกอบอาร์เรย์และพิมพ์อาร์เรย์ในลำดับที่เรียงแล้ว ตัวอย่างเช่น
ตัวอย่างอินพุต 1
arr[] = {-3, -1, 0, 1, 4, 6}
เอาต์พุต
{0, 1, 1, 9, 16, 36}
คำอธิบาย
กำลังสองของแต่ละองค์ประกอบของอาร์เรย์ที่กำหนด [-3, -1, 0, 1, 4, 6] คือ [9, 1, 0, 1, 16, 36] หลังจากเรียงลำดับจะได้ [0, 1, 1, 9, 16, 36]
ตัวอย่างอินพุต 2
arr[] = {0, 1, 2, 8, 9}
เอาต์พุต
{0, 1, 4, 64, 81}
วิธีการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราสามารถใช้วิธี Two-Pointer Approach ใน Two-Pointer เราใช้สองตัวชี้คือ left และ right ตัวชี้ left เริ่มต้นที่องค์ประกอบแรกของอาร์เรย์ และตัวชี้ right ชี้ไปที่องค์ประกอบสุดท้ายของอาร์เรย์
ขณะวนลูปผ่านองค์ประกอบของอาร์เรย์ เราจะหากำลังสองของค่าและตรวจสอบว่ากำลังสองของจำนวนเต็มทางขวา มากกว่าหรือน้อยกว่าจำนวนเต็มทางซ้าย
- รับอินพุตอาร์เรย์ของจำนวนเต็มในลำดับเพิ่มขึ้น
- ฟังก์ชัน integer squareAndSort(vector<int>& arr) รับอินพุตเป็นอาร์เรย์ของจำนวนเต็มและคืนค่ากำลังสองของแต่ละองค์ประกอบของอาร์เรย์ในลำดับที่เรียงแล้ว
- เริ่มต้นตัวชี้สองตัว left และ right ด้วยองค์ประกอบทางซ้ายและทางขวาสุดของอาร์เรย์
- พิมพ์กำลังสองขององค์ประกอบและเปรียบเทียบกับกำลังสองขององค์ประกอบทางขวา
- เพิ่มและลดตัวชี้ left และ right ตามลำดับ
ตัวอย่างโค้ด
#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) {
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;
}
ผลลัพธ์
การรันโค้ดด้านบนจะสร้างเอาต์พุตเป็น
0 1 1 9 16 36
กำลังสองของแต่ละองค์ประกอบของอาร์เรย์คือ 9, 1, 0, 1, 16, 36 หลังจากเรียงลำดับองค์ประกอบเหล่านี้ เอาต์พุทจะเป็น 0 1 1 9 16 36
