C/C++教程

leetcode算法刷题记录之颜色分类

本文主要是介绍leetcode算法刷题记录之颜色分类,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
/**
 * 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
 * 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * 
 * 
 * 示例1:
 * 输入:nums = [2,0,2,1,1,0]
 * 输出:[0,0,1,1,2,2]
 * 
 * 解题思路:
 * 1.双指针 p0,p2,p0从左向右移动,p2从右向左移动,
 * 2.nums[i]==0,与p0交换
 * 2.当nums[i]==2,与p2交换,直到nums[i]!=2,停止与p2交换
 *     如果此时nums[i] == 0,如上与p0交换;nums[i] == 1,不做处理。
 *
 */

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var n = nums.length;
    if(n==0) return;
    var p0=0,p2=n-1;
    for(var i=0;i<=p2;++i){
        while(i<=p2&&nums[i]==2){
            swap(nums,i,p2);
            p2--;
        }
        if(nums[i] == 0){
            swap(nums,i,p0);
            p0++;
        }
    }
};

function swap(nums,a,b){
    var temp;
    temp = nums[b];
    nums[b] = nums[a];
    nums[a] = temp;
}
var nums = [2,0,2,1,1,0,2];
sortColors(nums);
console.log(nums);

 

这篇关于leetcode算法刷题记录之颜色分类的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!