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

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

【题解】《算法零基础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. 最小时间差

原题链接: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. 有序数组的平方

原题链接: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. 优势洗牌

原题链接: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. 救生艇

原题链接: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;
    }
};
end

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

作者:英雄哪里出来

谢谢大家收看~

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5610986.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存