三色排序

╰半橙微兮° 2022-06-09 01:52 109阅读 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 条评论，109人围观）

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

相关阅读

相关 Java实现：三色球问题

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

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

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

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

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

相关色环互补色

![请添加图片描述][a0cd18bc52254d11bf7f7ca5a608ca28.jpeg] ![请添加图片描述][8651e2eed85f49669de8ce341

忘是亡心i/ 2024年03月16日 16:54/ 0 赞/ 20 阅读

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

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

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

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

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

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

相关物体色三刺激值计算

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

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

相关三色排序

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

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

相关排序算法（三）----选择排序

选择排序来自百度百科：选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在

蔚落/ 2022年03月19日 07:14/ 0 赞/ 139 阅读

相关初等排序（三）：选择排序

选择排序法作为一种非常直观的排序方法，会在每一个计算步骤中选出一个最小值，依次选出，进而完成排序。 selectionSort(A,N) //包含N个元素的0起点

迷南。/ 2022年02月24日 04:04/ 0 赞/ 157 阅读

相关项目4：三色球问题

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

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