LeetCode #912:Sort an Array(排序数组)

题目描述

题意基本上就是把 “默写快排” 四个大字给拍脸上了,调用标准库的 sort 在面试中肯定是没分的【手动狗头
需要注意的是测试用例中存在有序的长数组,如果直接取第一个元素作为快排的枢轴会超时,这里我在每次划分的时候取区间中间的元素作为枢轴来避免超时。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        qSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void qSort(vector<int>& nums, int low, int high) {
        if(low < high) {
            int p = partition(nums, low, high);
            qSort(nums, low, p - 1);
            qSort(nums, p + 1, high);
        }
    }

    int partition(vector<int>& nums, int low, int high) {
        swap(nums[low], nums[(low + high) / 2]); //选择中间的元素作为枢轴,避免有序长数组的Test Case超时
        int temp = nums[low];
        while(low < high) {
            while(low < high && nums[high] >= temp) high--;
            swap(nums[low], nums[high]);
            while(low < high && nums[low] <= temp) low++;
            swap(nums[low], nums[high]);
        }
        nums[low] = temp;
        return low;
    }
};

发表评论

您的电子邮箱地址不会被公开。