意外理解“计数排序”算法

引言

在刷leetcode的时候,遇到了一个数组的基础题“高度检查器”。简单来说,这道题的要求是 在一组 非递减 的数组中,查找出位置不正确的元素的数量

解法也很多啦,但主要的思路就是先构建一个与原数组元素相同,但有序递增的新数组。最后再与旧数组对比。但排序的算法是非常多,总体可以分为两类,一类是基于元素比较的排序,一类是非基于元素比较的排序 。我最先想到的解法是将原数组clone一份,然后使用Arrays.sort(arr)进行排序;后面看了其他人的解法,恍然大悟,并意外get到统计排序的精髓。

统计排序(又名计数排序)

统计排序就是非比较排序的一种排序方式,下面代码的heightChecker方法中的实现就是对 heights 数组进行统计排序的具体实现。
通过代码可以得到统计排序的复杂度信息:

k是数据范围,n是数据量。例如:{2,2,2,10000},n = 2,k = 10000 ;

时间复杂度 O(n+k)
空间复杂度 O(k)

计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。而且,计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

Show Me The Code

public class HeightChecker {
    public static void main(String[] args) {
        int[] arr = {1, 1, 4, 2, 1, 3};
        HeightChecker heightChecker = new HeightChecker();
        int i = heightChecker.heightChecker(arr);
        System.out.println(i);
    }

    public int heightChecker(int[] heights) {
        // 构建个新数组
        int[] arr = new int[101];

        for (int i : heights) {
            // 旧数组中的元素作为新数组的下标,
            // 当遇到相同的元素时,新数组中下标对应的值就加一。
            arr[i]++;
        }

        int count = 0;
        // 新旧数组进行比较
        for (int i = 0, j = 0; i < arr.length; i++) {
            while (arr[i] > 0) {
                if (i != heights[j]) {
                    count++;
                }
                arr[i]--;
                j++;
            }
        }
        return count;
    }
}

Related Posts

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© All Right Reserved