leetcode 164. Maximum Gap | 164. 最大间距（桶排序）

港控/mmm° 2022-09-11 01:14 18阅读 0赞

## 题目 ##

[https://leetcode.com/problems/maximum-gap/][https_leetcode.com_problems_maximum-gap]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

桶排序，用数组模拟桶  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        public int maximumGap(int[] nums) { 
            int N = nums.length;
            int digits = 0; // 最大位数
            for (int n : nums) { 
                digits = Math.max(digits, String.valueOf(n).length());
            }
            String[] arr = new String[N];
            for (int i = 0; i < N; i++) { 
                arr[i] = String.format("%0" + digits + "d", nums[i]);
            }
    
            String[] bucket = arr;
            for (int i = digits - 1; i >= 0; i--) { 
                String[] newBucket = new String[arr.length];
                int[] count = new int[10];
                int[] pos = new int[10];
                for (int j = 0; j < N; j++) { 
                    count[bucket[j].charAt(i) - '0']++;
                }
                for (int j = 1; j < 10; j++) { 
                    pos[j] = pos[j - 1] + count[j - 1];
                }
                // fill bucket
                for (int j = 0; j < N; j++) { 
                    newBucket[pos[bucket[j].charAt(i) - '0']++] = bucket[j];
                }
                bucket = newBucket;
            }
            int res = 0;
            for (int i = 1; i < N; i++) { 
                res = Math.max(res, Integer.parseInt(bucket[i]) - Integer.parseInt(bucket[i - 1]));
            }
            return res;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_maximum-gap]: https://leetcode.com/problems/maximum-gap/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/7b9ff3f089e04b83be2794fdd4011575.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/c116e715c84742768314bce152288e36.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/5f8f75dde800459bacfdc0a00662f72b.png