湘潭做网站价格 d磐石网络关于搜索引擎的搜索技巧

164.最大间距

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。

示例一：

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例二：

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

示例三：

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

解法一：排序直接莽（复习一下归并）

class Solution {
public:
void mergesort(vector<int>&nums,int beg,int end){if(beg>=end)return;int mid=beg+(end-beg)/2;mergesort(nums,beg,mid);mergesort(nums,mid+1,end);vector<int>nums2(nums.begin()+mid+1,nums.begin()+end+1);merge(nums,beg,mid,end,nums2,end-mid);}
void merge(vector<int>&nums1,int beg,int mid,int end,vector<int>&nums2,int n){int right=end+1,cur1=mid,cur2=n-1;while(1){if(cur1==beg-1&&cur2==-1)return ;else if(cur1==beg-1&&cur2!=-1){right--;nums1[right]=nums2[cur2];cur2--;}else if(cur1!=beg-1&&cur2==-1)return ;else if(nums1[cur1]>=nums2[cur2]){right--;nums1[right]=nums1[cur1];cur1--;}else if(nums1[cur1]<nums2[cur2]){right--;nums1[right]=nums2[cur2];cur2--;}}}int maximumGap(vector<int>& nums) {int n=nums.size();if(n==0||n==1)return 0;mergesort(nums,0,n-1);int jie=INT_MIN;for(int i=1;i<nums.size();i++)jie=max(jie,abs(nums[i]-nums[i-1]));return jie;}
};

解法二（基数排序）：

补充：基数排序三步走
1.找出数组中最大的数字的位数 maxDigitLength
2.获取数组中每个数字的基数（按高位计数）
3.遍历 maxDigitLength 轮数组，每轮按照基数对其进行排序

class Solution {
public:
void radixsort(vector<int>&nums){int n=nums.size();int maxNum=*max_element(nums.begin(),nums.end());   // 计算最大数字的长度int maxBit=1,num=10;// 计算最长数字的长度while(num<=maxNum){maxBit++;num*=10;}            vector<int>buf(n,0);for(int i=0,place=1;i<maxBit;i++,place*=10){vector<int>count(10,0);for(int j=0;j<n;j++){count[(nums[j]/place)%10]++;}for(int j=1;j<10;j++){count[j]+=count[j-1];}for(int j=n-1;j>=0;j--){int num=(nums[j]/place)%10;buf[count[num]-1]=nums[j];count[num]--;}copy(buf.begin(),buf.end(),nums.begin());// 计数排序完成后，将结果拷贝回 arr 数组}
}int maximumGap(vector<int>& nums) {int n=nums.size();int jie=0;radixsort(nums);for(int i=1;i<n;i++){jie=max(jie,nums[i]-nums[i-1]);}return jie;}
};

补充：
如果数组中包含负数，如何进行基数排序呢？
我们很容易想到一种思路：将数组中的每个元素都加上一个合适的正整数，使其全部变成非负整数，等到排序完成后，再减去之前加的这个数就可以了。
但这种方案有一个缺点：加法运算可能导致数字越界，所以必须单独处理数字越界的情况。
事实上，有一种更好的方案解决负数的基数排序。那就是在对基数进行计数排序时，申请长度为 19 的计数数组，用来存储 [-9, 9] 这个区间内的所有整数。在把每一位基数计算出来后，加上 9，就能对应上 counting 数组的下标了。也就是说，counting 数组的下标 [0, 18]对应基数 [-9, 9]。