-1

我正在尝试解决以下问题：

给定一个只有 3 个唯一数字 (1, 2, 3) 的数字数组，在 O(n) 时间内对列表进行排序。

示例 1：

输入：[3, 3, 2, 1, 3, 2, 1]

输出：[1、1、2、2、3、3、3]

挑战：尝试使用常量空间对列表进行排序

我可以使用额外空间的第一部分很简单，基本上我所做的是找到最小值、最大值和中间值，将它们作为键存储在 a 中hashmap，将它们的频率作为hashmap值，然后用正确的值填充新创建的数组：

import java.util.Map;
import java.util.HashMap;
class Testing{

    public static void sortArr(int[] arr){
        int[] newArr=new int[arr.length];
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>(3);
        int mini=minArr(arr);
        int maxi=maxArr(arr);
        int midNum=Integer.MAX_VALUE;
        
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }

        for(int num : hm.keySet()){
            if(num!=mini && num!=maxi){
                midNum=num;
                break;
            }
        }

        for(int i=0;i<arr.length;++i){
            if(i<hm.get(mini)){
                newArr[i]=mini;
            }else if(i>(arr.length-hm.get(maxi))){
                newArr[i]=maxi;
            }else{
                newArr[i]=midNum;
            }
        }

        for(int num : newArr){
            System.out.println(num);
        }
    }

    public static int minArr(int[] arr){
        int mini=Integer.MAX_VALUE;
        for(int num : arr){
            if(num<mini){
                mini=num;
            }
        }
        return mini;
    }

    public static int maxArr(int[] arr){
        int maxi=Integer.MIN_VALUE;
        for(int num : arr){
            if(num>maxi){
                maxi=num;
            }
        }
        return maxi;
    }


    public static void main(String args[]){
        int[] arr={-4,-4,9,9,-4,3,9,3,3,3,3,9,9,-4,9,3};
        sortArr(arr);
    }
}

我感兴趣的是挑战部分，我无法解决，感谢任何帮助，谢谢。

4

1 回答 1

2

如果您只想要最终结果，您可以使用三个计数器来完成。

  1. 数一数列表中的 1、2 和 3 的个数。
  2. 然后使用循环，从列表的第一个开始，用找到的计数写入数字

例如，您有 2 1、 22和 3 3。然后你循环数组并根据每个数字的计数器值从数组的第一个写入这些数字。

额外的空间是三个变量，是一个常数空间。此外，时间复杂度是Theta(n)我们循环遍历数组两次。

于 2019-10-07T10:39:51.883 回答