題目：https://leetcode-cn.com/problems/squares-of-a-sorted-array/
方法一：平方加排序
先對陣列的每一個元素進行平方，然后進行排序。
方法二：雙指標法：因為這是一個有序陣列，兩個指標分別指向最右邊和最左邊，然后兩者的平方值進行比較，然后將較大的放進最右邊。依次進行。
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int len = A.size();
vector<int>ans(len);
int a= 0, b= len - 1,i=len-1;
while (i >= 0)
{
int lef = A[a] * A[a]; int rig = A[b] * A[b];
if (lef > rig)
{
ans[i] = lef;
a++;
}
else ans[i] = rig, b--;
i--;
}
return ans;
}
};
方法二：二分找到邊界，然后進行擴展
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int len = A.size();
vector<int>ans;
int l = -1, r = len - 1, mid = 0;
while (l < r)
{
mid =(int) (l + r + 1) >> 1;
int len = A.size();
if (A[mid] <= 0) l = mid;
else r = mid - 1;
}
r = l + 1;
for (int i = 0; i < len; i++) {
if (l < 0) {
ans.push_back(A[r] * A[r]);
r++;
}
else if (r >= len) {
ans.push_back(A[l] * A[l]);
l--;
}
else {
if ((A[l] * A[l]) <= (A[r] * A[r])) {
int temp = A[l] * A[l];
ans.push_back(temp);
l--;
}
else {
ans.push_back((A[r] * A[r]));
r++;
}
}
}
for (int i = 0; i < ans.size(); i++)
{
cout <<ans[i] << " ";
}
return ans;
}
};
期間遇到的問題 起初定義vector<int>ans 時定義成vector<int>ans（len），輸出結果全是0；這是由于vector里面的函式push_back 在vector類中作用為在vector尾部加入一個資料。
其實等同于犯的如下錯誤：
const int size = 7;
int ia[ size ] = { 0, 1, 1, 2, 3, 5, 8 };
vector< int > ivec( size );
for ( int ix = 0; ix < size; ++ix )
ivec.push_back( ia[ ix ]);
程式結束時ivec 包含 14 個元素, ia 的元素從第八個元素開始插入。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/104801.html
標籤：C++ 語言