LeetCode 热题 100 JavaScript--75. 颜色分类

这篇具有很好参考价值的文章主要介绍了LeetCode 热题 100 JavaScript--75. 颜色分类。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:

输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:

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

提示:

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶:

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

var swamp = function(nums,i,j){
    var temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
} 
var sortColors = function(nums) {
    var left = 0,right = nums.length - 1
    var current = 0

    while(current<=right){
        if(nums[current]==0){
            swamp(nums,current,left)
            left++
            current++
        }else if(nums[current]==2){
            swamp(nums,current,right)
            right --
            // current++
        }else{
            current++
        }
        // if(nums[current]==1){
        //     current++
        // }

    }
    return nums

};

2、冒泡排序

var sortColors = function(nums) {
    for(var i=0;i<nums.length-1;i++){
        for(var j =i+1;j<nums.length;j++){
            if(nums[i]>nums[j]){
                var temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
            }
        }
    }
    return nums

};

3、归并排序

var sortColors = function(nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums
};

function mergeSort(nums, left, right) {
    if (left < right) {
        const mid = Math.floor((left + right) / 2);
        mergeSort(nums, left, mid);    // 对左半部分进行归并排序
        mergeSort(nums, mid + 1, right); // 对右半部分进行归并排序
        merge(nums, left, mid, right);   // 合并两个排好序的子数组
    }
}

function merge(nums, left, mid, right) {
    const temp = new Array(right - left + 1);
    let i = left;
    let j = mid + 1;
    let k = 0;

    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = nums[i++];
    }

    while (j <= right) {
        temp[k++] = nums[j++];
    }

    for (let m = 0; m < temp.length; m++) {
        nums[left + m] = temp[m];
    }
}

// 4、快速排序文章来源地址https://www.toymoban.com/news/detail-652109.html

var sortColors = function(nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums
};
function quickSort(nums,left,right){
    if(left<right){
        var l = left,r = right
    var key = nums[l]
    while(l<r){
        while(l<r&&nums[r]>key){
            r--
        }
        if(l<r){
            nums[l++] = nums[r]
        }
        while(l<r&&nums[l]<key){
            l++
        }
        if(l<r){
            nums[r--] = nums[l]
        }
    }
    nums[l] = key
    quickSort(nums,left,l-1)
    quickSort(nums,l+1,right)
    // if(l-1>left){
    //     quickSort(nums,left,l-1)
    // }
    // if(l+1<right){
    //     quickSort(nums,l+1,right)
    // }
    }
}

到了这里,关于LeetCode 热题 100 JavaScript--75. 颜色分类的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode.75 颜色分类

    给定一个包含红色、白色和蓝色、共  n   个元素的数组  nums  , 原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数  0 、  1  和  2  分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。

    2024年02月11日
    浏览(46)
  • 【Leetcode】75.颜色分类

    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums , 原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 示例1: 示例

    2024年02月14日
    浏览(39)
  • leetcode - 75. 颜色分类(java)

    难度 - 中等 原题链接 - 颜色分类 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下

    2024年02月13日
    浏览(30)
  • 每日一题:LeetCode-75. 颜色分类

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月04日
    浏览(40)
  • 算法leetcode|75. 颜色分类(rust重拳出击)

    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums , 原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 n == nums.length

    2024年02月10日
    浏览(41)
  • LeetCode 热题 100 JavaScript -- 74. 搜索二维矩阵

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。

    2024年02月13日
    浏览(43)
  • LeetCode 热题 100 JavaScript --226. 翻转二叉树

    给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例 3: 输入:root = [] 输出:[] 提示: 树中节点数目范围在 [0, 100] 内 -100 = Node.val = 100

    2024年02月14日
    浏览(40)
  • LeetCode 热题 100 JavaScript--543. 二叉树的直径

    给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。

    2024年02月14日
    浏览(40)
  • 力扣hot100 颜色分类 双指针 滚动赋值

    Problem: 75. 颜色分类 描述你的解题方法 时间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( 1 ) O(1) O ( 1 ) 👨‍🏫 参考题解

    2024年01月18日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包