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