三色排序

╰半橙微兮° 2022-06-09 01:52 159阅读 0赞

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。

给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。

测试样例：
    [0,1,1,0,2,2],6
    返回：[0,0,1,1,2,2]

**我的提交**

# -*- coding:utf-8 -*-
    
    class ThreeColor:
        def sortThreeColor(self, A, n):
            # write code here
            zindex = -1
            tindex = n
            i = 0
            while i < tindex:
                if A[i] == 0:
                    zindex += 1
                    A[zindex], A[i] = A[i], A[zindex]
                    i += 1
                elif A[i] == 1:
                    i += 1
                else:
                    tindex -= 1
                    A[tindex], A[i] = A[i], A[tindex]
                print("i = " + str(i) + " -> " + str(A))
            return A
    
    if __name__ == '__main__':
        three = ThreeColor()
        print(three.sortThreeColor([1,2,0,2],4))

**参考答案**

import java.util.*;
    
    public class ThreeColor { 
        public int[] sortThreeColor(int[] A, int n) {
            if (A == null || A.length < 2) {
                return A;
            }
            int left = -1;
            int index = 0;
            int right = A.length;
            while (index < right) {
                if (A[index] == 0) {
                    swap(A, ++left, index++);
                } else if (A[index] == 2) {
                    swap(A, index, --right);
                } else {
                    index++;
                }
            }
            return A;
        }
    
        public void swap(int[] arr, int index1, int index2) {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java实现：三色球问题

Java实现：三色球问题文章目录 Java实现：三色球问题 1. 问题 2. 解决方案 3. 实现代码

素颜马尾好姑娘i/ 2024年03月30日 16:16/ 0 赞/ 75 阅读

相关 C语言实现：三色球问题

C语言实现：三色球问题文章目录 C语言实现：三色球问题 1. 问题 2. 解决方案 3. 实现代码 4

浅浅的花香味﹌/ 2024年03月30日 16:14/ 0 赞/ 132 阅读

相关 Golang GC三色标记算法介绍

介绍三色标记算法是一种用于垃圾回收（Garbage Collection）的算法，主要用于标记和回收不再使用的内存对象。它是一种基于追踪（tracing）的垃圾回收算法

待我称王封你为后i/ 2024年02月19日 11:01/ 0 赞/ 43 阅读

相关 CMS 三色标记【JVM调优】

文章目录 1. 垃圾回收器 2. CMS 原理 3. 三色标记算法 1. 垃圾回收器 > ① Serial：最原始的垃圾回

深碍√TFBOYSˉ_/ 2023年10月15日 17:02/ 0 赞/ 64 阅读

相关初级系列14.三色球问题

三色球问题问题描述一个口袋中放有12个球，已知其中3个是红的，3个是白的，6个是黑的，现从中任取8个，问共有多少种可能的颜色搭配? 问题分析根据问题描述可设任

比眉伴天荒/ 2023年10月09日 10:32/ 0 赞/ 55 阅读

相关 python 三色球问题

2. 三色球问题有红、黄、蓝三种颜色的求，其中红球 3 个，黄球 3 个，绿球 6 个。先将这 12 个球混合放在一个盒子中，从中任意摸出 8

妖狐艹你老母/ 2023年07月16日 11:59/ 0 赞/ 23 阅读

相关三色标记算法和浮动垃圾

三色标记在并发标记的过程中，因为标记期间应用线程还在继续跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。这里我们引入“ 三色标记 ”来给大家解释下，把Gc

阳光穿透心脏的1/2处/ 2022年09月13日 06:21/ 0 赞/ 201 阅读

相关物体色三刺激值计算

物体色三刺激值计算实例物体色三刺激值计算实例\_郑眼观色\_新浪博客 http://blog.sina.com.cn/s/blog\_4b892b790102v59n.

左手的ㄟ右手/ 2022年08月08日 06:42/ 0 赞/ 146 阅读

相关三色排序

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等

╰半橙微兮°/ 2022年06月09日 01:52/ 0 赞/ 160 阅读

相关项目4：三色球问题

问题及代码： /\ \copyright (c) 2014,烟台大学计算机学院 \All rights reserved. \文件名称：test.cpp

妖狐艹你老母/ 2021年06月10日 20:41/ 0 赞/ 365 阅读