双指针法又一感悟-526互联

最开始做的时候没想到双指针法，用了简单的冒泡排序结果超时了，题解中的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;
    }
};