最开始做的时候没想到双指针法,用了简单的冒泡排序结果超时了,题解中的sort函数用的是快排。
点击查看代码
void quick_sort(int a[], int l, int r)
{
if (l < r)
{
int i,j,x;
i = l;
j = r;
x = a[i];
while (i < j)
{
while(i < j && a[j] > x)
j--; // 从右向左找第一个小于x的数
if(i < j)
a[i++] = a[j];
while(i < j && a[i] < x)
i++; // 从左向右找第一个大于x的数
if(i < j)
a[j--] = a[i];
}
a[i] = x;
quick_sort(a, l, i-1); /* 递归调用 */
quick_sort(a, i+1, r); /* 递归调用 */
}
}
得到快速排序的思路后,还是有问题,我没有新建一个数组,而是进行交换,这导致left就没动,并不是一趟选出最大的那个,所以应该要新建应该数组
点击查看代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int>v(nums.size(),0);int n=nums.size();
int left=0;int right=n-1;
for(int i=n-1;i>=0;i--){
if(nums[left]*nums[left]>nums[right]*nums[right]){
v[i]=nums[left]*nums[left];
++left;
}
else {
v[i]=nums[right]*nums[right];
--right;
}
}
return v;
}
};