LeetCode 高级算法之排序与搜索

我就是我 2022-12-27 09:09 119阅读 0赞

[324. Wiggle Sort II][]

这一题主要有两个知识点, 分别是快速选择, 3路分类, 分别对应了leecode里的[215. Kth Largest Element in an Array][] 和 [75. Sort Colors][]问题

其中的第K大元素利用快速排序的原理可以快速找到第K大元素的位置, 时间复杂度O(n)

模板代码如下:

class Solution {
    public:
        int ans;
        void quickSelect(vector<int>&nums, int start, int end, int k)
        {
            
            int left = start, right = end;
            int pivot = nums[start];
            while (left<right)
            {
                while (left<right && nums[right]>=pivot) --right;  //注意这里的>=号很关键
                if (left<right) nums[left++] = nums[right];
                while (left<right && nums[left]<=pivot) ++left;    //<=号也很关键
                if (left<right) nums[right--] = nums[left];
            } 
            nums[left] = pivot;
            if (left==k) {
                ans = nums[left]; return;
            }
            if (left > k) quickSelect(nums, start, left, k);
            else quickSelect(nums, left+1, end, k);
        }
        int findKthLargest(vector<int>& nums, int k) {
            int size = nums.size();
            quickSelect(nums, 0, size-1, size-k);
            return ans;
        }
    };

注意边界条件的选择是>= 和 <=

75题的三路排序问题, 通用模板如下:

class Solution {
    public:
        void sortColors(vector<int>& nums) {
            int left = 0, right = nums.size()-1;
            int i = 0;
            while (i<=right)
            {
                if (nums[i] > 1)
                {
                    swap(nums[i], nums[right--]);        // 大于中间数的在右边, 注意这里i没有+1
                }
                else if (nums[i] < 1)
                {
                    swap(nums[i++], nums[left++]);        // 小于中间数的在左边, 这里i要+1
                }
                else {
                    ++i;        //等于中间数的情况, 不做交换
                }
            }
            return;
        }
    };

利用这两个模板可以把大于中位数的数放在其右边, 小于中位数的在左边, 然后讲左右两半数字逆序逐个放入到原数组中就形成了摆动排序的效果

[378. Kth Smallest Element in a Sorted Matrix][]

这个题目有两个知识点:

1. 这种sorted Matrix 的遍历方法是从左下或者右上开始, 从左下角开始的数, 大于它的都在右边, 小于它的都在上边, 这样可以在同类题型中使用回溯或者动态规划的方法, 这题里用到的是二分查找

2. 第K大或者第K小的数有通用的方法是堆排序, 本题可以建立一个大小为K的小根堆, 把数依次从不同行或者列中取出再找下一个入队, 堆排序的两个知识点

堆排序的两个知识点:
    1. C++中priority_queue的template写法, 
    priority_queue< datatype, container<datatype>, cmp >
    三个参数分别是数据类型, 数据容器类型(一般是非关联容器), 以及比较函数, 这里的比较函数用的是函数对象, 所以该参数的写法要不就写一个cmp类重载括号()运算符, 要不就auto 一个lambda函数将该函数作为参数初始化为函数对象
    (1) struct cmp{
        bool operator()(const datatype&a ,const datatype& b) {
            return a < b;
        }
    }
    
    (2) auto cmp = [](const dataype&a , const datatype& b){
        return a < b;
    }
        priority_queue<datatype, container<datatype>, decltype(cmp)>myque(cmp);
    
    
    2. 堆排序的手写, 几个步骤,
    (1) 三个步骤, heapify, 从上到下建堆, 交换
    (2) 堆的初始化, 从size/2开始(第一个非叶子节点), 直到根节点, 自上而下建堆
    (3) 堆排序的过程, 根部数据与最后一个数据交换位置, 如果是小根堆, 比较函数选择greater<type>, 因为最小的数是在尾部的, 就相当于从大到小排序;
    或者换一种理解思路, 比较函数的两个参数分别是子节点和父节点,  子节点greater than 父节点, 就是小根堆 
    
    void maxHeapify(vector<int>& nums, int i, int len) {
            for (; (i << 1) + 1 <= len;) {
                int lson = (i << 1) + 1;
                int rson = (i << 1) + 2;
                int large;
                if (lson <= len && nums[lson] > nums[i]) {
                    large = lson;
                } else {
                    large = i;
                }
                if (rson <= len && nums[rson] > nums[large]) {
                    large = rson;
                }
                if (large != i) {
                    swap(nums[i], nums[large]);
                    i = large;
                } else {
                    break;
                }
            }
        }
        void buildMaxHeap(vector<int>& nums, int len) {
            for (int i = len / 2; i >= 0; --i) {
                maxHeapify(nums, i, len);
            }
        }
        void heapSort(vector<int>& nums) {
            int len = (int)nums.size() - 1;
            buildMaxHeap(nums, len);
            for (int i = len; i >= 1; --i) {
                swap(nums[i], nums[0]);
                len -= 1;
                maxHeapify(nums, 0, len);
            }
        }
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/sort-an-array/solution/pai-xu-shu-zu-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[4. Median of Two Sorted Arrays][]

这题的细节比较多, 在使用二分查找的过程中, 我们要找的是第K小的数, 而不是下标为K的数, 前后差的1很可能对结果有影响

class Solution {
    public:
        int findKthElement(vector<int>& nums1, vector<int>& nums2, int start1, int start2, int k)
        {
            /*
            注意点1, 当一个数组已经遍历完毕, 直接返回另一个数组的第K个数 
            */
            if (start1>=nums1.size()) return nums2[start2+k-1];
            if (start2>=nums2.size()) return nums1[start1+k-1];
            if (k==1) return min(nums1[start1], nums2[start2]);
            int m = nums1.size(), n = nums2.size();
            /*
            注意点2, 当start + k/2 越界时, 不能直接到该数组的结尾, 还是要用结尾的数据与另一个数组的start+k/2 比较
            */
            int pos1 = min(start1 + k/2 - 1, m-1);
            int pos2 = min(start2 + k/2 - 1, n-1);      
            if (nums1[pos1]<=nums2[pos2])
            {
                k = k - (pos1-start1+1);
                return findKthElement(nums1, nums2, pos1+1, start2, k);
            }
            else {
                k = k - (pos2-start2+1);
                return findKthElement(nums1, nums2, start1, pos2+1, k);
            }
    
    
        }
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int size1 = nums1.size(), size2= nums2.size();
            int size = size1 + size2;
            /*
            注意点3, size为奇数时找第k/2+1大的数, size为偶数时要两个数的平均值
            */
            if (size%2)
            {
                return findKthElement(nums1, nums2, 0, 0, size/2+1);
            }
            else{
                double k1 = findKthElement(nums1, nums2, 0, 0, size/2);
                double k2 = findKthElement(nums1, nums2, 0, 0, size/2+1);
                return (k1+k2)/2.0 ;
            }
        }
    };

[324. Wiggle Sort II]: https://leetcode-cn.com/problems/wiggle-sort-ii/
[215. Kth Largest Element in an Array]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[75. Sort Colors]: https://leetcode-cn.com/problems/sort-colors/
[378. Kth Smallest Element in a Sorted Matrix]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
[4. Median of Two Sorted Arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/