【题解】《算法零基础100讲》(第37讲) 排序进阶 - 快速排序

虽然是介绍递归形式的快速排序， 但是做题时都用的C++ STL的sort()，面试时可得手写啊。

• 前言
• 快速排序
• • 原理
  • 规则
  • 代码实现
• 习题
• 539. 最小时间差
• • 分析
  • 代码
• 977. 有序数组的平方
• • 分析
  • 代码
• 870. 优势洗牌
• • 分析
  • 代码
• 881. 救生艇
• • 分析
  • 代码
• end

递归形式详解：快速排序C语言实现

每次找到基准值，以基准值为分界线，左边的值全部比基准值小，右边的值全部比基准值大。

1. 从右向左找比基准值小的数据，找到后放到左边；
2. 从左向右找比基准值大的数据，找到后放到右边；
3. 重复 1、2操作，如果 left == right （下标），循环退出，再将基准值放到nums[left]或nums[right]。

#include
#include
#include

static void Quick(int* nums, int left, int right);
static int Partition(int* nums, int left, int right);

void Quick_Sort(int* nums, int numsSize)
{
	assert(nums != NULL);

	Quick(nums, 0, numsSize - 1);
}

static void Quick(int* nums, int left, int right)
{
	if (left < right) 
	{
		int par = Partition(nums, left, right);

		if (left < par - 1)
		{
			Quick(nums, left, par - 1);
		}

		if (par + 1 < right) 
		{
			Quick(nums, par + 1, right);
		}
	}
}
static int Partition(int* nums, int left, int right)
{
	
	int key = nums[left];  

	//重复三个规则
	while (left < right) 
	{
		while (left < right && nums[right] > key) 
			right--;
		if (left == right) 
		{
			break;
		}
		nums[left] = nums[right];  

		while (left < right && nums[left] < key) 
			left++;
		if (left == right) 
		{
			break;
		}
		nums[right] = nums[left]; 
	}

	nums[left] = key; //nums[right] = key

	return left; //return right
}

详细过程可看上面链接的文章。。

原题链接：539. 最小时间差

做法是

1. 先申请一个等长的整型数组；
2. 将原字符串数组中的串依次转为整数存放在新的数组中；
3. 遍历新数组，找出最小时间差；
4. 遍历后得出的最小答案，再考虑 00：00 和23：59的情况。

class Solution {
public:
    int findMinDifference(vector& timePoints)
    {
        int n = timePoints.size();
        
        //1
        int timeArray[n];
        memset(timeArray, 0, sizeof(timeArray));
	
		//2
        for (int i = 0; i < n; ++i)
        {
            timeArray[i] = stoi(timePoints[i].substr(0, 2)) * 60 + stoi(timePoints[i].substr(3, 2));
        }
		
		//3
        sort(timeArray, timeArray + n);

        int ans = 1440, tmp = 1440;
        for (int i = 0; i < n - 1; ++i)
        {
            tmp = timeArray[i + 1] - timeArray[i];
            ans = min(tmp, ans);
        }
		
		//4
        int err = 24 * 60 + timeArray[0] - timeArray[n - 1];

        return min(ans, err);
    }
};

对应的四个步骤，很容易理解。。

原题链接：977. 有序数组的平方

先依次平方，再排序

class Solution {
public:
    vector sortedSquares(vector& nums)
    {
        int n = nums.size();
        
        for (int i = 0; i < n; ++i)
        {
            nums[i] *= nums[i];
        }

        sort(nums.begin(), nums.end(), less());
        return nums;
    }
};

原题链接：870. 优势洗牌

将A、B排序，每次取A B中未使用的最大值进行比较。
但要知道哪个元素未使用，需要记住每个元素的下标。

这里就需要利用C++的 pair

pair可以将 2个数据 组合成 一组数据，两个数据可以分别用pair的 两个公有函数 first 和 second访问。

将nums1和打包后的nums2按照从大到小排序

class Solution {
public:
    vector advantageCount(vector& nums1, vector& nums2)
    {
        int n = nums1.size();
        
        vector> sorted(n);
        for (int i = 0; i < sorted.size(); ++i)
        {
            sorted[i] = {nums2[i], i};
        }

        sort(nums1.begin(), nums1.end(), greater());
        sort(sorted.begin(), sorted.end(), [](const auto& a, const auto& b){return a.first > b.first;});

        vector ans(n);
        int left = 0, right = n - 1;

        for (int i = 0; i < n; ++i)
        {
            auto[cur, index] = sorted[i];
            if (nums1[left] <= cur)
            {
                ans[index] = nums1[right--];
            }
            else
            {
                ans[index] = nums1[left++];
            }
        }

        return ans;
    }
};

原题链接：881. 救生艇

先对所有人的体重进行排序；
那可以以这种方式来做：
首先排除最重的人比救生艇的承重还要重。。。

1. 如果最轻的人和最重的人体重加起来不超过救生艇的承重，那就可以把他们两个放在一个救生艇上，然后排除这两个人，再从剩下的人里按照这样的方法来；
2. 如果超过了承重，那就让最重的人独自乘坐一条救生艇，在之后分配时不考虑此人。

实现：
在排序后，利用两个指针，一个指向最轻的人，一个指向最重的，按照上面的方式，遇到情况1，将首指针++， 尾指针–；遇到情况2，只将尾指针-- 。

class Solution {
public:
    int numRescueBoats(vector& people, int limit)
    {  
        sort(people.begin(), people.end(), less());

        int ans = 0;
        int light = 0, heavy = people.size() - 1;

        while (light <= heavy)
        {
            if (people[light] + people[heavy] > limit)
            {
                --heavy;
            }
            else
            {
                ++light;
                --heavy;
            }
            ++ans;
        }

        return ans;
    }
};

原文链接：《算法零基础100讲》(第37讲) 排序进阶 - 快速排序

作者：英雄哪里出来

谢谢大家收看~