内容简介:作者: 码蹄疾毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者;负责小米应用商店、日历、开屏广告业务线研发;
作者: 码蹄疾
毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者;
负责小米应用商店、日历、开屏广告业务线研发;
主导小米广告引擎多个模块重构;
关注推荐、搜索、广告领域相关知识;
题目
给定一个包含红色、白色和蓝色,一共 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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- LeetCode 第 75 号问题:颜色分类
- 颜色搭配及颜色科学
- CSS教程:图片使用混合模式和颜色叠加filter滤镜,改变PNG图标颜色
- OpenGL ES入门: 渲染金字塔 - 颜色、纹理、纹理与颜色混合填充以及GLKit实现
- WebGL 纹理颜色原理
- Sass 内置颜色方法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Machine Learning in Action
Peter Harrington / Manning Publications / 2012-4-19 / GBP 29.99
It's been said that data is the new "dirt"—the raw material from which and on which you build the structures of the modern world. And like dirt, data can seem like a limitless, undifferentiated mass. ......一起来看看 《Machine Learning in Action》 这本书的介绍吧!