专栏首页脑洞前端75. 颜色分类

75. 颜色分类

题目描述

给定一个包含红色、白色和蓝色,一共 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

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

其实就是排序,而且没有要求稳定性,就是用啥排序算法都行。题目并没有给出数据规模,因此我默认数据量不大,直接选择了冒泡排序

关键点解析

冒泡排序的时间复杂度是N平方,无法优化,但是可以进一步优化常数项, 比如循环的起止条件。由于每一次遍历都会将最后一位“就位”,因此内层循环的截止条件就可以是 nums.length-i, 而不是 nums.length, 可以省一半的时间。

代码

/*
 * @lc app=leetcode id=75 lang=javascript
 *
 * [75] Sort Colors
 *
 * https://leetcode.com/problems/sort-colors/description/
 *
 * algorithms
 * Medium (41.41%)
 * Total Accepted:    297K
 * Total Submissions: 716.1K
 * Testcase Example:  '[2,0,2,1,1,0]'
 *
 * Given an array with n objects colored red, white or blue, sort them in-place
 * so that objects of the same color are adjacent, with the colors in the order
 * red, white and blue.
 *
 * Here, we will use the integers 0, 1, and 2 to represent the color red,
 * white, and blue respectively.
 *
 * Note: You are not suppose to use the library's sort function for this
 * problem.
 *
 * Example:
 *
 *
 * Input: [2,0,2,1,1,0]
 * Output: [0,0,1,1,2,2]
 *
 * Follow up:
 *
 *
 * A rather straight forward solution is a two-pass algorithm using counting
 * sort.
 * First, iterate the array counting number of 0's, 1's, and 2's, then
 * overwrite array with total number of 0's, then 1's and followed by 2's.
 * Could you come up with a one-pass algorithm using only constant space?
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
function swap(nums, i, j) {
const temp = nums[i];
       nums[i] = nums[j];
       nums[j] = temp;
}
for(let i = 0; i < nums.length - 1; i++) {
for(let j = 0; j < nums.length - i; j++) {
if(nums[j] < nums[j -1]) {
                swap(nums, j - 1, j)
}

}
}
};

本文分享自微信公众号 - 脑洞前端(fe_lucifer)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 219. 存在重复元素 II

    给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为...

    lucifer210
  • 47. 全排列 II

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations-ii 著作权归领扣网络所有。商...

    lucifer210
  • 46. 全排列

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载...

    lucifer210
  • Array - 283. Move Zeroes

    Given an array nums, write a function to move all 0's to the end of it while mai...

    用户5705150
  • C++错误解决:double free or corruption (out): 0x00000000011abe70 ***

    博主最近疯狂的迷恋上了leetcode刷题,想要锻炼脑力和算法思想的,推荐去这个网站上刷题。因为是用c++编写的,而且提交的时候会经常遇到一些报错。比如题目的这...

    十里桃花舞丶
  • leetCode163|数组中两元素的最大乘积

    给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-1) 取得最大值。

    码农王同学
  • LeetCode第四天

    leetcode 第四天 2018年1月4日 15.(628)Maximum Product of Three Numbers ? JAVA class Sol...

    郭耀华
  • LeetCode81|移动零

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    码农王同学
  • LeetCode 283:移动零 Move Zeroes

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    爱写bug
  • 数据结构算法操作试题(C++/Python)——下一个排列

    leetcode 链接:https://leetcode-cn.com/problems/next-permutation/

    莫斯

扫码关注云+社区

领取腾讯云代金券