164. 最大间距

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

程序核心思想

题目中说要在线性时间复杂度和空间复杂度下完成这个题目。可以考虑用桶排序来做。
如果给定len个数，那么准备len+1个桶。最小的数进0号桶，最大的数进最后一个桶，然后每个数进相应的桶（每个桶代表一定的范围，代码见下方）。对于每个桶记录3个值：最小值、最大值、是否有值。这样，i号桶的最小值跟i-1号桶的最大值便是挨着的了。所以最大间距不可能会出现在桶的内部，因为必定存在一个空桶，所以求出相邻的非空桶之间的差值，最大的即为最大间距。

Tips

难点是如何确定一个数该进哪个桶？代码为return (int) ((num - min) * len / (max - min));
但是还是发现有错误，结果是因为一个数据类型的原因，把numd的数据类型从int改为long即可。

代码

class Solution {
    public int maximumGap(int[] nums) {
                
        int len = nums.length;
        if(len < 2)     return 0;
        int min = nums[0];
        int max = nums[0];
        for(int i = 0; i < len; i++){
            if(nums[i] < min)   min = nums[i];
            if(nums[i] > max)   max = nums[i];
        }
        if(min == max)  return 0;
        
        int[] BuckMin = new int[len + 1];
        int[] BuckMax = new int[len + 1];
        boolean[] BuckBool = new boolean[len + 1];
        
        
        for (int i = 0; i < len; i++) {
            int loc = bucket(nums[i], len, min, max);
             if(BuckBool[loc] == true){
                if(BuckMax[loc] < nums[i])  BuckMax[loc] = nums[i];
                if(BuckMin[loc] > nums[i])  BuckMin[loc] = nums[i];
            }else{
                BuckBool[loc] = true;
                BuckMin[loc] = nums[i];
                BuckMax[loc] = nums[i];
            }
        }
                
        int answer = 0;
        int cur = BuckBool.length - 1;
        while(cur > 0){
            for(int i = cur - 1; i >= 0; i--){
                if(BuckBool[i] == true){
                    int temp = BuckMin[cur] - BuckMax[i];
                    if(temp > answer)   answer = temp;
                    cur = i;
                    break;  
                }else{
                    continue;
                }
            }
        }
        
        return answer;
    }
    
    public static int bucket(long num, int len, int min, int max) {
        return (int) ((num - min) * len / (max - min));
    }
}