LeetCode 164 Maximum Gap 桶排序与基数排序

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

先看题，简单地说就是给一个未排序的数组，排一下续，然后算出相邻2个数的最大值。

熟悉我的人都知道，我就是个懒蛋，于是就有了下面的代码：

public int maximumGap(int[] nums) {
    if (nums==null||nums.length<2)
        return 0;
    Arrays.sort(nums);
    int max = 0;
    for (int i = 0; i < nums.length-1 ; i++)
        max = Math.max(max, Math.abs(nums[i + 1] - nums[i]));
    return max;
}

虽然过了 仔细一看题目啊 不对啊 要求线性的时间复杂度和空间复杂度啊。

妥妥的桶排序，或者基数排序啊。

桶排序是什么意思呢？

就是准备n个桶，两个桶的间距是固定的，然后把要排序的数按照顺序先扔到特定桶里，

在桶内再使用别的方法排序或者递归排序。

简单的说{1,4,3,5,2,6,9,8,7,10},假如有5个桶，每个桶间距是2，那么首先把数字扔到桶里

1号桶[1,3) :1,2

2号桶[3,5) :4,3
3号桶[5,7) :5,6
4号桶[7,9) :8,7
5号桶[9,11):9,10

桶内排序之后：
1号桶[1,3) :1,2
2号桶[3,5) :3,4
3号桶[5,7) :5,6
4号桶[7,9) :7,8
5号桶[9,11):9,10

在把每个桶里面的数字按照顺序顺次连接起来，这样排序就完成了。
那么，问题来了，谁来决定有多少个桶，和桶的范围呢？
其实是由数组内最大值，最小值，和数组长度决定的，
令 数组中最大值=max，最小值=min，数组长度=len
则 桶的范围 bucketRange = int((max - min - 1) / (len - 1)) + 1

   桶的个数 bucketLen = (max - min) / bucketRange + 1



为啥 这样呢？ 微积分和离散数学自己算去。



至于基数排序，就是10个桶，按照数位依次排序，可以从低位向高位（LSD），

也可以从高位向低位排序（MSD）

百度这个例子已经给的很好了，而且附有代码，直接复制粘贴过来

原链接：百度-基数排序



第一步


以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39




第二步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93




第三步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。


第一步


以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39




第二步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93




第三步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。













LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

相对于nlgn的直接排序算法，如果数量级过大，使用桶排序或者基数排序这两种现行排序，还是很有必要的。

关于Leetcode 207 Course Schedule的一点思考...

马上就要硕士毕业了，闲来无事 刷一刷代码，今天做了一个比较有意思的题 LeetCode 207 Course Schedule.

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

链接：https://leetcode.com/problems/course-schedule/

一个图的题 拓扑排序嘛~ DFS一下， 看能不能找到环， 或者找到入度为0的点 一个一个删掉。

首先来看DFS：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    ArrayList<Integer>[] map = new ArrayList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        map[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < prerequisites.length; i++) { // pre -> vertex        

        map[prerequisites[i][1]].add(prerequisites[i][0]);
    }
    int[] visitState = new int[numCourses];
    Arrays.fill(visitState, 0); // 0: unvisited, 1: visiting, 2:visited    

        for (int i = 0; i < numCourses; i++) {
        if (!DFSVisit(i, map, visitState))
            return false;
    }
    return true;
}

private static boolean DFSVisit(int n, ArrayList<Integer>[] map, int[] visitState) {
    if (visitState[n] == 2)
        return true;
    if (visitState[n] == 1)
        return false;
    visitState[n] = 1;
    for (int j = 0; j < map[n].size(); j++) {
        if (!DFSVisit(map[n].get(j), map, visitState))
            return false;
    }
    visitState[n] = 2;
    return true;

}

下面是删除入度为0的点的方式：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    HashMap<Integer,Point> hashMap = new HashMap<>();
    for (int i = 0; i < numCourses ; i++) {
        Point point = new Point(i);
        hashMap.put(i,point);
    }
    for (int[] record:prerequisites)
    {
        hashMap.get(record[0]).getOut().add(record[1]);
        hashMap.get(record[1]).getIn().add(record[0]);
    }
    while (true)
    {
        int pointIdx = findNoInDegree(hashMap);
        if (pointIdx==-1)
        {
            for (Point point:hashMap.values())
            {
                if (point.getIn().size()!=0)
                    return false;
            }
            return true;
        }
        else        {
            Point point = hashMap.get(pointIdx);
            for (int idx: point.getOut())
            {
                hashMap.get(idx).getIn().remove(pointIdx);
            }
            hashMap.remove(pointIdx);
        }
    }
}

public int findNoInDegree(HashMap<Integer,Point> hashMap)
{
    for (Integer key: hashMap.keySet())
    {
        if (hashMap.get(key).getIn().size()==0)
            return key;
    }
    return -1;
}

class Point
{
    int num = 0;
    HashSet<Integer> in;
    HashSet<Integer> out;

    Point(int num)
    {
        this.num = num;
        this.in = new HashSet<>();
        this.out = new HashSet<>();
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public HashSet<Integer> getOut() {
        return out;
    }

    public void setOut(HashSet<Integer> out) {
        this.out = out;
    }

    public HashSet<Integer> getIn() {
        return in;
    }

    public void setIn(HashSet<Integer> in) {
        this.in = in;
    }
}

比较而言，很明显 第一种方式效率高于第二种，但是第二种方式不免冗杂了些，但是在其他方面，

作为一个程序员的话，哪一种方式好一些呢。

在学校这一年半的学习生涯中，几乎所有的课程（eg：Design Pattern，Software Product Line，

Software Maintenance and Evolutionary）都在强调一点 "Do not think about performance"

那么Performance 到底算是什么呢...
其实就个人理解，performance就是钱，security啦，user friendliness啦，Maintainability啦，就像是商品，用performance去买。
当然花多少，怎么花由产品特性和技术标准决定。