LeetCode通关:通过排序一次秒杀五道题,舒服!

发表于 2年以前  | 总阅读数:364 次

刷题路线参考:https://github.com/chefyuan/algorithm-base

大家好,我是拿输出博客督促自己刷题的老三,前面学习了十大排序:[万字长文|十大基本排序,一次搞定!] ,接下来我们看看力扣上有没有什么能拿排序解决的题目吧!

排序基础

简单了解一下基本的排序——

基本排序分类:

排序分类

基本排序性能:

排序方法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(n) O(1) 稳定
希尔排序 O(n^(1.3-2)) O(n²) O(n) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n) 稳定
桶排序 O(n+k) O(n²) O(n) O(n+k) 稳定
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) 稳定

更具体的可以查看:[万字长文|十大基本排序,一次搞定!] 好了,开始我们愉快的刷题之旅吧!

刷题现场

LeetCode912. 排序数组

☕ 题目:912. 排序数组 (https://leetcode-cn.com/problems/sort-an-array/)

❓ 难度:中等

描述:给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

思路:

这道题如果用api,一行就搞定了——Arrays.sort(nums),那面试官的反应多半是,门在那边,慢走不送。

所以,毫无疑问,我们要手撕排序了。

如果对排序算法不太熟,可以上一个冒泡排序,但是这个明显只能说中规中矩,所以,我们选择:

手撕快排

关于快排,就不多讲。

直接上代码:

class Solution {
    public int[] sortArray(int[] nums) {
       quickSort(nums,0,nums.length-1);
       return nums;
    }

    public void quickSort(int[] nums,int left, int right){
     //结束条件
      if(left>=right){
        return;
      }
      //分区
      int partitionIndex=partition(nums,left,right);
      //递归左分区
      quickSort(nums,left,partitionIndex-1);
      //递归右分区
      quickSort(nums,partitionIndex+1,right);
    }

    public int partition(int[] nums,int left,int right){
        //基准值
        int pivot=nums[left];
        //mark标记下标
        int mark=left;
        for(int i=left+1;i<=right;i++){
            if(nums[i]<pivot){
                //小于基准值,则mark后移,并交换位置
                mark++;
                int temp=nums[mark];
                nums[mark]=nums[i];
                nums[i]=temp;
            }
        }
        //把基准值放到mark的位置
        nums[left]=nums[mark];
        nums[mark]=pivot;
        return mark;
    }
}
  • 时间复杂度:快排时间复杂度O(nlogn)

有时间的可以把十大排序都在这道题练上一练。

LeetCode347. 前 K 个高频元素

☕ 题目:347. 前 K 个高频元素(https://leetcode-cn.com/problems/top-k-frequent-elements/)

❓ 难度:中等

描述:

给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示:

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

**进阶:**你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

思路:

这道题第一思路是什么呢?

统计元素出现频率,从大到小排序,取前k个元素。

我们想挑战一下进阶要求,时间复杂度优于O(nlogn),所以熟悉的冒泡、快排之类的比较类排序都不可用,只能使用非比较类的三种排序方法:计数排序、桶排序、基数排序。

这里我们选择HashMap+桶排序的方式。

使用HashMap存储元素出现频率,使用桶排序来进行排序。

代码如下:

   public int[] topKFrequent(int[] nums, int k) {
        //使用HashMap存储元素出现频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //桶
        List<Integer>[] buckets = new List[nums.length + 1];
        //往桶里添加元素出现次数
        for (Integer key : map.keySet()) {
            //根据出现频率决定元素入哪个桶
            int count = map.get(key);
            //初始化桶
            if (buckets[count] == null) buckets[count] = new ArrayList<>();
            //将元素存到桶中
            buckets[count].add(key);
        }
        //结果列表
        List<Integer> result = new ArrayList<>();
        //取倒数k个非空桶中的元素
        for (int i = buckets.length - 1; k > 0; i--) {
            if (buckets[i] != null) {
                //取出桶中的元素
                for (Integer num : buckets[i]) {
                    result.add(num);
                    k--;
                }
            }
        }
        //将列表中的元素赋给数组
        int[] res = new int[result.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = result.get(i);
        }
        return res;
    }
  • 时间复杂度:这道题用了桶排序,时间复杂度O(n)。

剑指 Offer 45. 把数组排成最小的数

☕ 题目:剑指 Offer 45. 把数组排成最小的数 (https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)

❓ 难度:中等

描述:

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

思路:

稍微分析一下这道题,发现这道题其实也是一道排序题。

只要我们把数组里的元素按照某种规则进行排序。

现在的问题就是这个排序规则是什么呢?

因为需要拼接字符串,以[3,30]为例,“3”+“30”=“330”,“30”+"3"="303",330>303,那么我们就可以说3大于30。

所以定义规则:

  • 若拼接字符串 x+y>y+x ,则 x 大于y ;
  • 反之,若拼接字符串 x+y<y+x ,则 x 小于 y ;

规则图如下(来源参考[2):

图片来源参考[2]

那么,这道题我们就知道怎么写了。

用我们自定义的排序规则从小到大排序数组。

排序方法我们选择快排,所以这道题就是自定义排序+快排

代码如下:

    public String minNumber(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        //结果
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(String.valueOf(num));
        }
        return sb.toString();
    }

    //快排
    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int partionIndex = partion(nums, left, right);
        quickSort(nums, left, partionIndex - 1);
        quickSort(nums, partionIndex + 1, right);
    }

    public int partion(int[] nums, int left, int right) {
        int pivot = nums[left];
        int mark = left;
        for (int i = left + 1; i <= right; i++) {
            if (lessThan(nums[i], pivot)) {
                mark++;
                int temp = nums[mark];
                nums[mark] = nums[i];
                nums[i] = temp;
            }
        }
        nums[left] = nums[mark];
        nums[mark] = pivot;
        return mark;
    }

    //自定义大小比较规则
    public boolean lessThan(int x, int y) {
        String sx = String.valueOf(x), sy = String.valueOf(y);
        return (sx + sy).compareTo(sy + sx) < 0;
    }

写的比较臃肿,但比较清晰。

有一种利用内置排序来实现的写法,不太建议:

    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x));
        StringBuilder ans = new StringBuilder();
        for(String s : strs)
            ans.append(s);
        return ans.toString();
    }
  • 时间复杂度:O(nlogn)。

有一道题:179. 最大数 和这道题基本一样。

剑指 Offer 51. 数组中的逆序对

☕ 题目:剑指 Offer 51. 数组中的逆序对 (https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)

❓ 难度:困难

描述:

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

思路:

这一道题是困难,有没有被吓住?

其实这道题如果用归并排序的思路去解决的话,就没有想象中的那么难。

归并排序这里就不讲了。

解决这道题,我们只需要在归并排序的基础上,加上对逆序对的统计:

归并+逆序对统计示意图(图片来源参考[3]):

归并+逆序对统计(图片来源参考[3])

现在的关键点是,归并的过程如何计算逆序对个数?

我们可以看一下,合并的时候,l指向左子数组2的位置,r指向右子数组0的位置,num[l]>nums[r],因为子数组是有序的,所以l后面几个元素也都一定大于0,所以可以得出,此时逆序对数量=mid-l+1。

归并计算逆序对

代码如下:

class Solution {
    //统计逆序对
    int count = 0;

    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return count;
    }

    //归并排序
    public void mergeSort(int[] nums, int left, int right) {
        //结束
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        //左半部分
        mergeSort(nums, left, mid);
        //右半部分
        mergeSort(nums, mid + 1, right);
        //合并
        merge(nums, left, mid, right);
    }

    //合并
    public void merge(int[] arr, int left, int mid, int right) {
        //临时数组
        int[] tempArr = new int[right - left + 1];
        //指向左右子数组指针
        int l = left, r = mid + 1;
        int index = 0;
        //把左右子数组较小元素放入到临时数组
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                tempArr[index++] = arr[l++];
            } else {
                //增加一行,统计逆序对
                count += (mid - l + 1);
                tempArr[index++] = arr[r++];
            }
        }
        //将左子数组剩余的元素拷贝到临时数组
        while (l <= mid) {
            tempArr[index++] = arr[l++];
        }
        //将右边子数组剩余的元素拷贝到临时数组
        while (r <= right) {
            tempArr[index++] = arr[r++];
        }
        //将临时数组的元素拷贝给原数组
        for (int i = 0; i < tempArr.length; i++) {
            arr[i + left] = tempArr[i];
        }
    }
}
  • 时间复杂度:归并排序时间复杂度O(nlogn)。

LeetCode147. 对链表进行插入排序

☕ 题目:剑指 Offer 51. 数组中的逆序对 (https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)

❓ 难度:困难

描述:

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。

插入排序算法:

  1. 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
  3. 重复直到所有输入数据插入完为止。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路:

这道题不只是插入排序,还涉及到链表的操作,关于链表,可以查看:[LeetCode通关:听说链表是门槛,这就抬脚跨门而入]

  • 关于插入排序:我们需要从未排序序列里将元素插入到排序序列的合适位置

插入排序

  • 关于链表插入:链表插入是插入节点前驱节点改变后继的一个操作,为了头插也能统一,通常我们会加一个虚拟头节点

链表插入

  • 所以,综合起来,我们需要标记有序序列和无序序列的分界点,遍历无序序列的时候,记录前驱,当需要将无序序列插入到有序序列的时候,遍历有序序列,找到插入位置,先删除该节点,再插入

链表插入排序

代码如下:

   public ListNode insertionSortList(ListNode head) {
        if (head == null && head.next == null) {
            return head;
        }
        //虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //记录有序序列终点
        ListNode last = head;
        //遍历无序序列
        ListNode after = head.next;
        while (after != null) {
            if (last.val <= after.val) {
                after = after.next;
                last = last.next;
                continue;
            }
            //遍历有序序列,查找插入位置
            ListNode prev = dummy;
            while (prev.next.val <= after.val) {
                prev = prev.next;
            }
            //找到插入位置
            //删除无序序列节点
            last.next = after.next;
            //插入有序序列
            after.next = prev.next;
            prev.next = after;
            //继续移动
            after=last.next;
        }
        return dummy.next;
    }
  • 时间复杂度:O(n²)。

总结

熟悉的顺口溜总结:

总结

简单的事情重复做,重复的事情认真做,认真的事情有创造性地做。


参考:

[1]. https://github.com/chefyuan/algorithm-base

[2]. https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/

[3]. https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/

本文由哈喽比特于2年以前收录,如有侵权请联系我们。
文章来源:https://mp.weixin.qq.com/s/v0A1jIxsl7mW-MW1cyK21Q

 相关推荐

刘强东夫妇:“移民美国”传言被驳斥

京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而,京东官方通过微博发言人发布的消息澄清了这些传言,称这些言论纯属虚假信息和蓄意捏造。

发布于:1年以前  |  808次阅读  |  详细内容 »

博主曝三大运营商,将集体采购百万台华为Mate60系列

日前,据博主“@超能数码君老周”爆料,国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。

发布于:1年以前  |  770次阅读  |  详细内容 »

ASML CEO警告:出口管制不是可行做法,不要“逼迫中国大陆创新”

据报道,荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦(ASML)CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。

发布于:1年以前  |  756次阅读  |  详细内容 »

抖音中长视频App青桃更名抖音精选,字节再发力对抗B站

今年早些时候,抖音悄然上线了一款名为“青桃”的 App,Slogan 为“看见你的热爱”,根据应用介绍可知,“青桃”是一个属于年轻人的兴趣知识视频平台,由抖音官方出品的中长视频关联版本,整体风格有些类似B站。

发布于:1年以前  |  648次阅读  |  详细内容 »

威马CDO:中国每百户家庭仅17户有车

日前,威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”,同时,他发文表示:中国汽车普及率低于非洲国家尼日利亚,每百户家庭仅17户有车。意大利世界排名第一,每十户中九户有车。

发布于:1年以前  |  589次阅读  |  详细内容 »

研究发现维生素 C 等抗氧化剂会刺激癌症生长和转移

近日,一项新的研究发现,维生素 C 和 E 等抗氧化剂会激活一种机制,刺激癌症肿瘤中新血管的生长,帮助它们生长和扩散。

发布于:1年以前  |  449次阅读  |  详细内容 »

苹果据称正引入3D打印技术,用以生产智能手表的钢质底盘

据媒体援引消息人士报道,苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后,3D系统一度大涨超10%,不过截至周三收盘,该股涨幅回落至2%以内。

发布于:1年以前  |  446次阅读  |  详细内容 »

千万级抖音网红秀才账号被封禁

9月2日,坐拥千万粉丝的网红主播“秀才”账号被封禁,在社交媒体平台上引发热议。平台相关负责人表示,“秀才”账号违反平台相关规定,已封禁。据知情人士透露,秀才近期被举报存在违法行为,这可能是他被封禁的部分原因。据悉,“秀才”年龄39岁,是安徽省亳州市蒙城县人,抖音网红,粉丝数量超1200万。他曾被称为“中老年...

发布于:1年以前  |  445次阅读  |  详细内容 »

亚马逊股东起诉公司和贝索斯,称其在购买卫星发射服务时忽视了 SpaceX

9月3日消息,亚马逊的一些股东,包括持有该公司股票的一家养老基金,日前对亚马逊、其创始人贝索斯和其董事会提起诉讼,指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。

发布于:1年以前  |  444次阅读  |  详细内容 »

苹果上线AppsbyApple网站,以推广自家应用程序

据消息,为推广自家应用,苹果现推出了一个名为“Apps by Apple”的网站,展示了苹果为旗下产品(如 iPhone、iPad、Apple Watch、Mac 和 Apple TV)开发的各种应用程序。

发布于:1年以前  |  442次阅读  |  详细内容 »

特斯拉美国降价引发投资者不满:“这是短期麻醉剂”

特斯拉本周在美国大幅下调Model S和X售价,引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金(Future Fund)管理合伙人加里·布莱克发帖称,降价是一种“短期麻醉剂”,会让潜在客户等待进一步降价。

发布于:1年以前  |  441次阅读  |  详细内容 »

光刻机巨头阿斯麦:拿到许可,继续对华出口

据外媒9月2日报道,荷兰半导体设备制造商阿斯麦称,尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效,但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。

发布于:1年以前  |  437次阅读  |  详细内容 »

马斯克与库克首次隔空合作:为苹果提供卫星服务

近日,根据美国证券交易委员会的文件显示,苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元(约 4.65 亿元人民币)。用于在 2023-2025 年期间,发射卫星,进一步扩展苹果 iPhone 系列的 SOS 卫星服务。

发布于:1年以前  |  430次阅读  |  详细内容 »

𝕏(推特)调整隐私政策,可拿用户发布的信息训练 AI 模型

据报道,马斯克旗下社交平台𝕏(推特)日前调整了隐私政策,允许 𝕏 使用用户发布的信息来训练其人工智能(AI)模型。新的隐私政策将于 9 月 29 日生效。新政策规定,𝕏可能会使用所收集到的平台信息和公开可用的信息,来帮助训练 𝕏 的机器学习或人工智能模型。

发布于:1年以前  |  428次阅读  |  详细内容 »

荣耀CEO谈华为手机回归:替老同事们高兴,对行业也是好事

9月2日,荣耀CEO赵明在采访中谈及华为手机回归时表示,替老同事们高兴,觉得手机行业,由于华为的回归,让竞争充满了更多的可能性和更多的魅力,对行业来说也是件好事。

发布于:1年以前  |  423次阅读  |  详细内容 »

AI操控无人机能力超越人类冠军

《自然》30日发表的一篇论文报道了一个名为Swift的人工智能(AI)系统,该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。

发布于:1年以前  |  423次阅读  |  详细内容 »

AI生成的蘑菇科普书存在可致命错误

近日,非营利组织纽约真菌学会(NYMS)发出警告,表示亚马逊为代表的电商平台上,充斥着各种AI生成的蘑菇觅食科普书籍,其中存在诸多错误。

发布于:1年以前  |  420次阅读  |  详细内容 »

社交媒体平台𝕏计划收集用户生物识别数据与工作教育经历

社交媒体平台𝕏(原推特)新隐私政策提到:“在您同意的情况下,我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”

发布于:1年以前  |  411次阅读  |  详细内容 »

国产扫地机器人热销欧洲,国产割草机器人抢占欧洲草坪

2023年德国柏林消费电子展上,各大企业都带来了最新的理念和产品,而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。

发布于:1年以前  |  406次阅读  |  详细内容 »

罗永浩吐槽iPhone15和14不会有区别,除了序列号变了

罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品,具体内容为:“以我对我‘子公司’的了解,我认为 iPhone 15 跟 iPhone 14 不会有什么区别的,除了序(列)号变了,这个‘不要脸’的东西,这个‘臭厨子’。

发布于:1年以前  |  398次阅读  |  详细内容 »
 相关文章
Android插件化方案 5年以前  |  237271次阅读
vscode超好用的代码书签插件Bookmarks 2年以前  |  8108次阅读
 目录