題目

輸入一個整數數組职抡，實現一個函數來調整該數組中數字的順序葬燎，使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分缚甩，并保證奇數和奇數谱净，偶數和偶數之間的相對位置不變。請嘗試在線性時間復雜度和空間復雜度的條件下解決此問題擅威。

程序核心思想

題目中說要在線性時間復雜度和空間復雜度下完成這個題目壕探。可以考慮用桶排序來做郊丛。
如果給定len個數李请，那么準備len+1個桶。最小的數進0號桶厉熟，最大的數進最后一個桶导盅，然后每個數進相應的桶（每個桶代表一定的范圍，代碼見下方）揍瑟。對于每個桶記錄3個值：最小值白翻、最大值、是否有值绢片。這樣滤馍，i號桶的最小值跟i-1號桶的最大值便是挨著的了。所以最大間距不可能會出現在桶的內部底循，因為必定存在一個空桶巢株，所以求出相鄰的非空桶之間的差值，最大的即為最大間距熙涤。

Tips

難點是如何確定一個數該進哪個桶阁苞？代碼為return (int) ((num - min) * len / (max - min));
但是還是發(fā)現有錯誤，結果是因為一個數據類型的原因祠挫，把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));
    }
}