GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — 颜色分类-75 · Issue #28 · sl1673495/leetcode-javascript

颜色分类-75 #28

New issue
Copy link
New issue
Copy link
Open
Open
颜色分类-75#28
Copy link
Labels
排序

Description

@sl1673495
sl1673495
opened on May 12, 2020
Issue body actions

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

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

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

计数排序

最简单的思路就是遍历一遍整个数组,统计出其中各个颜色的数量,最后把这个数组重新填充即可。

let sortColors = function(nums) {
    let colors = [0, 0, 0]

    for (let i = 0; i < nums.length; i++) {
        colors[nums[i]] ++
    }

    nums.length = 0
    for (let i = 0; i < colors.length; i++) {
        for(let j = 0; j < colors[i]; j++) {
            nums.push(i)
        }
    }
};

Activity

  1. sl1673495
    added
    排序
    on May 12, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    排序

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      You are visitor 01402520 — GeezerVison does not store the pages you look up.
      Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.