977.有序數(shù)組的平方
給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組川陆，要求也按 非遞減順序 排序。
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]遵蚜，排序后苦始，數(shù)組變?yōu)?[0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104-
nums已按 非遞減順序 排序
進(jìn)階：
- 請(qǐng)你設(shè)計(jì)時(shí)間復(fù)雜度為
O(n)的算法解決本問(wèn)題
思路：
這道題拿到手寞钥，第一反應(yīng)肯定是，可以使用最簡(jiǎn)單的方法陌选，將數(shù)組中的所有元素進(jìn)行平方處理理郑，構(gòu)建新數(shù)組，再進(jìn)行排序柠贤。
然而香浩，這肯定不是最優(yōu)解，這道題同樣也可以嘗試使用雙指針?lè)ㄟM(jìn)行求解臼勉。
暴力求解：
將每個(gè)數(shù)平方后邻吭，再進(jìn)行排序，這里不光要用到一個(gè)for循環(huán)宴霸，還需要用到sort函數(shù)囱晴，所以時(shí)間復(fù)雜度為O(n + nlogn)膏蚓，可以看作是O(nlogn)
注：運(yùn)用sort函數(shù)需要加上algorithm頭文件
class Solution {
public:
//暴力平方
vector<int> sortedSquares(vector<int>& A) {
for (int i = 0; i < A.size(); i++) {
A[i] *= A[i]; //將數(shù)組中每個(gè)數(shù)平方
}
sort(A.begin(), A.end()); // 快速排序
return A;
}
};
雙指針?lè)ǎ?/h2>
對(duì)于數(shù)組，雙指針?lè)ㄊ且环N十分常用的方法畸写，而這道題我們也可以嘗試使用雙指針?lè)ㄟM(jìn)行求解驮瞧。
這里有個(gè)十分關(guān)鍵的點(diǎn)，就是：原本的數(shù)組本身就是有序的枯芬，是一個(gè)非遞減的數(shù)組论笔，那么即使數(shù)組中元素有正有負(fù)，絕對(duì)值最大的元素肯定是在數(shù)組的兩端的千所，即數(shù)組平方的最大值是在數(shù)組的兩端的狂魔。
所以我們可以使用兩個(gè)雙指針i,j一個(gè)指向起始位置，一個(gè)指向數(shù)組的末尾淫痰。
定義一個(gè)新的數(shù)組result用于儲(chǔ)存新的有序平方后的元素最楷。
這里有兩條重要的判斷語(yǔ)句：
- 如果
A[i] * A[i] < A[j] * A[j]那么result[k--] = A[j] * A[j];。 - 如果
A[i] * A[i] >= A[j] * A[j]那么result[k--] = A[i] * A[i];待错。
class Solution {
public:
//雙指針
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1; //指向新數(shù)組的末尾籽孙，從后往前賦值
vector<int> result(A.size(), 0);
for (int i = 0, j = A.size() - 1; i <= j;) { // 注意這里要i <= j，因?yàn)樽詈笠幚韮蓚€(gè)元素
if (A[i] * A[i] < A[j] * A[j]) { //判斷條件1：尾部元素更大
result[k--] = A[j] * A[j];
j--;
}
else {
result[k--] = A[i] * A[i]; //判斷條件2：頭部元素更大
i++;
}
}
return result;
}
};
時(shí)間復(fù)雜度為O(n)火俄。
后續(xù)也會(huì)堅(jiān)持更新我的LeetCode刷題筆記犯建，歡迎大家關(guān)注我，一起學(xué)習(xí)烛占。
如果這篇文章對(duì)你有幫助胎挎，或者你喜歡這篇題解，可以給我點(diǎn)個(gè)贊哦忆家。
CSDN同步更新犹菇，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學(xué)習(xí)筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主
往期回顧：
LeetCode844.比較含退格的字符串
LeetCode283.移動(dòng)零
LeetCode27.移除元素
LeetCode26.刪除有序數(shù)組中的重復(fù)項(xiàng)
