草庐IT

leetcode 75. Sort Colors 颜色分类

okokabcd 2023-03-28 原文

一、题目大意

链接：https://leetcode.cn/problems/sort-colors

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你可以不使用代码库中的排序函数来解决这道题吗？
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

二、解题思路

两个思路，一是用桶排序，先统计频率，再按key排序，最后提取结果。另一种思路，因为值的话就3个是已经确定的，遍历数组0往数组最左边放，2往最右边放，遍历完数组就排好了。

三、解题方法

3.1 Java实现-桶排序

public class Solution {
    public void sortColors(int[] nums) {
        // 统计频率
        Map<Integer, Integer> seqMap = new HashMap<>();
        for (int tmp : nums) {
            seqMap.put(tmp, seqMap.getOrDefault(tmp, 0) + 1);
        }

        // 按key排序
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
        for (Map.Entry<Integer, Integer> entry : seqMap.entrySet()) {
            priorityQueue.add(entry);
        }

        // 提取结果
        int idx = nums.length - 1;
        while (!priorityQueue.isEmpty()) {
            Map.Entry<Integer, Integer> entry = priorityQueue.poll();
            for (int i = 0; i < entry.getValue(); i++) {
                nums[idx--] = entry.getKey();
            }
        }
    }
}

3.2 Java实现-另一种思路

public class Solution2 {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        // 注意结束条件是 i<=right
        for (int i = 0; i <= right; i++) {
            if (nums[i] == 0) {
                swap(nums, i, left++);
            } else if (nums[i] == 2) {
                // 注意此时i要呆在原地，因为for里面会执行i++,此时做i--做消减
                swap(nums, i--, right--);
            }
        }
    }

    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

四、总结小记

  • 2022/5/24 用固定的套路桶排序解题耗时2毫秒，用另一种思路耗时不到1毫秒，虽然耗时少但我们还要掌握固定套路。
leetcodeColorsnumsInteger解题算法与数据结构

有关leetcode 75. Sort Colors 颜色分类的更多相关文章

  1. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  2. ruby 诅咒颜色 - 2

    如何使用Ruby的默认Curses库获取颜色？所以像这样:puts"\e[0m\e[30;47mtest\e[0m"效果很好。在浅灰色背景上呈现漂亮的黑色。但是这个:#!/usr/bin/envrubyrequire'curses'Curses.noecho#donotshowtypedkeysCurses.init_screenCurses.stdscr.keypad(true)#enablearrowkeys(forpageup/down)Curses.stdscr.nodelay=1Curses.clearCurses.setpos(0,0)Curses.addstr"Hello

  3. ruby - Rails 3 的 RGB 颜色选择器 - 2

    状态:我正在构建一个应用程序，其中需要一个可供用户选择颜色的字段，该字段将包含RGB颜色代码字符串。我已经测试了一个看起来很漂亮但效果不佳的。它是“挑剔的颜色”，并托管在此存储库中:https://github.com/Astorsoft/picky-color.在这里我打开一个关于它的一些问题的问题。问题:请建议我在Rails3应用程序中使用一些颜色选择器。 最佳答案 也许页面上的列表jQueryUIDevelopment:ColorPicker为您提供开箱即用的产品。原因是jQuery现在包含在Rails3应用程序中，因此使用基

  4. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  5. ruby - 如何使用 Ruby 基于字母数字字符串生成颜色？ - 2

    我想要像“嘿那里”这样的东西变成，例如，#316583。我希望将任意长度的字符串“归结”为十六进制颜色。我不知道从哪里开始。我在想，每个字符串的MD5散列都是不同的-但如何将该散列转换为十六进制颜色数字？ 最佳答案 你可以只取几位前几位:require'digest/md5'color=Digest::MD5.hexdigest('Mytext')[0..5] 关于ruby-如何使用Ruby基于字母数字字符串生成颜色？，我们在StackOverflow上找到一个类似的问题：

  6. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  7. ruby - 256 种颜色，前景和背景 - 2

    这是两个脚本的故事，与previousquestion有关.这两个脚本位于http://gist.github.com/50692.ansi.rb脚本在所有256种背景颜色上显示所有256种颜色。ncurses.rb脚本显示所有256种前景颜色，但背景显示基本的16种颜色，然后似乎循环显示各种属性，如闪烁和反向视频。那么是什么给了？这是ncurses中的错误，它使用带符号的整数来表示颜色对吗？(即'tputcolors'表示256但'tputpairs'表示32767而不是65536)似乎如果是这种情况，颜色对的前半部分会正确显示但后半部分会重复或进入属性作为int包裹。

  8. ruby - RSpec Git Bash Windows——缺少颜色？ - 2

    我在Windows上使用GitBash来完成我的大部分Rails工作，每次我运行bundleexecrspecspec它都会提醒我“你必须geminstallwin32console才能使用Windows上的颜色”，然后以纯黑色和白色运行RSpec。但是我确实安装了win32console，当我在列表中运行gemlist时，它有win32console(1.3.0x86-mingw32)。RSpec工作正常，但我希望它有一些颜色。我用谷歌搜索了这个并找到了多种解决方案，但似乎没有一个适合我。有人可以写出在GitBashforWindows上使用RSpec获取颜色的“循序渐进”方法吗？

  9. ruby - Chromedriver `driver.manage.logs.get(:browser)` 在 chromedriver 75.0.3770.8 上失败 - 2

    在chromedriver75.0.3770.8上访问driver.manage.logs.get(:browser)-它导致错误#(NoMethodError)的未定义方法“日志”在74.0.3729.6上工作正常来自:https://github.com/SeleniumHQ/selenium/issues/7270 最佳答案 在最近的selenium-webdriver(4.4.0)和最近的Chrome(105)中，manage.logs不见了，但这有效:page.driver.browser.logs.get(:browse

  10. Ruby popen3 和 ANSI 颜色 - 2

    我正在尝试让watchr在文件更改时自动运行测试，并且得到了我需要工作的大部分内容，除了RSpec中的所有ANSI颜色都被忽略了这一事实。违规代码如下:stdin,stdout,stderr=Open3.popen3(cmd)stdout.each_linedo|line|last_output=lineputslineend当cmd等于rspecspec/**/*.rb时，上面的代码可以正常运行RSpec，除了所有输出都是单色的。我看过使用Kernel.system代替，但是系统不返回我需要确定测试是否失败/成功的输出。如何获取从Ruby中执行的脚本的输出(包括ANSI颜色)并将其输

随机推荐