【Leetcode】75.颜色分类

栏目: 编程工具 · 发布时间: 5年前

内容简介:作者: 码蹄疾毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者;负责小米应用商店、日历、开屏广告业务线研发;

作者: 码蹄疾

毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者;

负责小米应用商店、日历、开屏广告业务线研发;

主导小米广告引擎多个模块重构;

关注推荐、搜索、广告领域相关知识;

题目

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

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

注意:

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

示例:

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

进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。

你能想出一个仅使用常数空间的一趟扫描算法吗?

题解

首先这个题目你肯定不能用数数的方法啊,如果你用了相当于说:“面试官傻逼!”

那怎么来解这种问题呢?我给大家说说一个不是那么绝对的经验, 涉及到数组和链表的题目,先想想双指针法可不可以用

这个题目用三个指针:

index 表示当前遍历的元素

p1 记录最后一个0的位置

p2 记录最开始一个2的位置

然后从左到右便利,调整index、p1、p2元素

java版本

public void sortColors(int[] nums) {
        // 1-pass
        int p1 = 0, p2 = nums.length - 1, index = 0;
        while (index <= p2) {
            if (nums[index] == 0) {
                nums[index] = nums[p1];
                nums[p1] = 0;
                p1++;
            }
            if (nums[index] == 2) {
                nums[index] = nums[p2];
                nums[p2] = 2;
                p2--;
                index--;
            }
            index++;
        }
    }

python版本

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        p1 = 0
        p2 = len(nums) - 1
        index = 0
        while index <= p2:
            if nums[index] == 0:
                nums[index] = nums[p1]
                nums[p1] = 0
                p1 += 1
            if nums[index] == 2:
                nums[index] = nums[p2]
                nums[p2] = 2
                p2 -= 1
                index -= 1
            index += 1

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Computer Age Statistical Inference

Computer Age Statistical Inference

Bradley Efron、Trevor Hastie / Cambridge University Press / 2016-7-21 / USD 74.99

The twenty-first century has seen a breathtaking expansion of statistical methodology, both in scope and in influence. 'Big data', 'data science', and 'machine learning' have become familiar terms in ......一起来看看 《Computer Age Statistical Inference》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具