LeetCode排序颜色java

yzckvree 于 2023-02-02 发布在 Java

关注(0)|答案(3)|浏览(119)

我想用数组列表对nums[]进行排序，但是它只能通过17/83的情况，我不知道我哪里做错了。

public class Solution {
   public void sortColors(int[] nums) {
       List<Integer> list = new ArrayList<Integer>();
       List<Integer> redList = new ArrayList<Integer>();
       List<Integer> whiteList = new ArrayList<Integer>();
       List<Integer> blueList = new ArrayList<Integer>();

       if(nums==null||nums.length==0)
          return ;

       for(int number:nums){
           switch (number){
               case 0:
                  redList.add(number);
                  break;
               case 1:
                  whiteList.add(number);
                  break;
               case 2:
                  blueList.add(number);
                  break;
               default:
                  break;
           }
       }
       list.addAll(redList);
       list.addAll(whiteList);
       list.addAll(blueList);
   }
}

它占用了很多额外的空间，但我认为它可以比插入排序更快。

Java

来源：https://stackoverflow.com/questions/31126380/leetcode-sort-color-java

3条答案

按热度按时间

fykwrbwg1#

检查API到期日Collections.sort

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {

public static void main(String[] args) {
    //Must be Integer class
    Integer[] nums = { 1, 2, 3, 0, 1, 2, 3, 1, 4, 4, 4, 0, 0, 1, 2, 1, 0,
            0, 4 };

    List<Integer> list = Arrays.asList(nums);
    // Before sort
    System.out.println("Before sort :" + list.toString());

    // Sort 'list' items
    Collections.sort(list);
    // After sort
    System.out.println("After sort :" + list.toString());
}

输出：

Before sort :[1, 2, 3, 0, 1, 2, 3, 1, 4, 4, 4, 0, 0, 1, 2, 1, 0, 0, 4]
After sort :[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4]

赞(0）回复(0）举报 2023-02-02

vlju58qv2#

颜色排序问题分3步解决

方法

1.初始化低=0，中=0，高=数值长度-1;
1.检查nums[mid]与nums[low]，以及nums[mid]与nums[high]
1.比较后进行操作，如开关情况所示。

class Solution {
    public void sortColors(int[] nums) {
        if(nums.length==1){
            return;
        }
        int low=0,mid=0,high=nums.length-1;
        while(mid<=high){
            switch(nums[mid]){
                case 0:
                    int temp=nums[low];
                    nums[low]=nums[mid];
                    nums[mid]=temp;
                    mid++;
                    low++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    int temp1=nums[mid];
                    nums[mid]=nums[high];
                    nums[high]=temp1;
                    high--;
                    break;
                    
            }
        }
    }
}

赞(0）回复(0）举报 2023-02-02

wnvonmuf3#

也许你不应该在练习算法时使用内置函数：）
他们要求的算法是一个标准的3-way-quicksort或national-flag-sort或two-pivot-sort。非常好的解释是在这个链接：https://www.geeksforgeeks.org/3-way-quicksort-dutch-national-flag/
关键是要有两个枢轴，基本上你可以在一次迭代中就地排序数组。

Space complexity: O(1) (no extra space)
Time comlexity: O(n)

赞(0）回复(0）举报 2023-02-02

我来回答

LeetCode排序颜色java

3条答案

方法

相关问题

热门标签

最新问答