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.
这个题目最直接的方法就是sort, 然后找相邻相差最大的gap, 但是这样做的话时间复杂度是O（nlogn）, 这个题目大致的思想是排序，但是要求的是线性的时间， 并且可以有线性的space complexity， 线性排序算法有： counting sort，radix sort， bucket sort，
对于线性排序算法，要求输入是在一定的范围内的， 比如 0-maximum,线性排序也是典型的通过空间换取时间， 所以线性排序算法比较消耗空间。
1. counting sort :
分配一个maximum长度的数组， 存储对应位置元素出现的次数， 然后对这些次数从第一个元素开始累加， 累加的结果是当前元素在最后sorted array中的位置， 最后从数组的最后一个元素开始将其放置到正确的位置并且对应位置累计的counter -1 。
counting sort:
counting sort 只能对整数进行排序， 不能对浮点数进行排序，
2 . Radix sort
基数排序
基本思想：基数排序是将整数按位进行排序，从低位开始，对每一位使用稳定的排序算法如计数排序进行排序，直到最高位排序完成，所有元素排序完成。
在这里需要注意的是，我实现的基数排序是需要传入整数数组中位数最长的元素的位数。否则在对每一位进行排序时，仅将每个整数的那一位均为零作为程序结束的标志，将会出现如果测试数据的第某一位全为零，则算法执行停止，出现 Radix sort 只能针对整数进行排序，
3. bucket sort
被排序的数组的元素范围也是有一定要求，在minimal - maximum之间， 针对 maximum 和 minimal之间的差值， 以及array的元素个数，可以知道如果将整个array里面元素进行分段的话，每一段的gap是多少， gap = （maximum - minimal) / nums.size() + 1;
gap知道之后可以确定总共可以分出多少个bucket, numBucket = (maximum-minimal) /gap + 1, 也需要确定每一个元素是属于哪个bucket, bucketIdx = ( nums[i] - minimal) / gap；知道这些量之后，我们可以将每个元素存入到对应的bucket中，对于如果一个bucket有很多的元素，我们需要利用quick sort来对bucket里面的元素进行排序， 最后从第一个bucket里面依次取出元素就可以完成排序了。
time complexity: O (n)
这个题目所用的方法是bucket sort， 但是我们不需要把所有的元素都存到bucket里面， 只要维持一个bucket里面的minimal number 和 maximum number， 最后最大的gap一定是在前一个bucket的maximum value 和 后一个bucket的minimal value的差值中取。因为这两个元素最后是相邻的， 并且这两个元素的差值一定> gap,而一个bucket里面的相邻两个元素的差值是一定<=gap的。
为什么会想到用bucket sort? 因为bucket sort 的特点是对待排序的元素进行分区排序，每个区间内的元素的相差不超过这个gap, 而相邻区间的两个相邻元素的差值是一定超过这个gap的， 正好这个题目中要求相邻元素gap最大， 可以使用bucket sort来做。
leetcode上面对于线性排序算法的题目还是很少的， 感觉对于这些线性排序算法知道就好了， 不用太深究。
class Solution {
public:
//bucket sort
//# of buckets: (max-min)/gap + 1;
//gap : ceil ((max-min)/(# of elements)) in order to have at least 1 bucket
//each bucket store min value and max value
//iterate the bucket and find the different between the min and max value of adjacent bucket
int maximumGap(vector<int>& nums) {
//sanity check
if (nums.size() < 2) return 0;
//compute gap
int minv = INT_MAX;
int maxv = INT_MIN;
for (int i : nums) {
minv = min(i, minv);
maxv = max(i, maxv);
}
int gap = ((maxv - minv) / nums.size()) + 1;
int numBucket = (maxv - minv) / gap + 1;
vector<int> minmax(2, INT_MAX);
minmax[1] = INT_MIN;
vector<vector<int>> buckets(numBucket, minmax);
//store value in buckets
for (int i = 0; i < nums.size(); i++) {
int idx = (nums[i] - minv)/gap;
buckets[idx][0] = min(buckets[idx][0], nums[i]);
buckets[idx][1] = max(buckets[idx][1], nums[i]);
}
//compare adjacent bucket
int pre = 0;
int maxGap = INT_MIN;
for (int i = 1; i < buckets.size(); i++) {
if (buckets[i][0] == INT_MAX) continue; // empty bucket
maxGap = max(maxGap, buckets[i][0] - buckets[pre][1]);
pre = i;
}
return maxGap;
}
};
updated: more understandable solution
class Solution {
public:
int maximumGap(vector<int>& nums) {
if (nums.size() < 2) return 0;
int maxl = INT_MIN;
int minl = INT_MAX;
for (int i : nums) {
maxl = max(i, maxl);
minl = min(i, minl);
}
int gap = (maxl - minl) / nums.size() + 1;
int numBucket = (maxl - minl) / gap + 1;
vector<pair<int, int>> max_min(numBucket, make_pair(INT_MIN, INT_MAX));
for (int i : nums) {
int idx = (i-minl)/gap;
max_min[idx].first = max(max_min[idx].first, i);
max_min[idx].second = min(max_min[idx].second, i);
}
int global = INT_MIN;
pair<int, int> pre = max_min[0];
for (int i = 1; i < max_min.size(); i++) {
if (max_min[i].first != INT_MIN && max_min[i].second != INT_MAX) {
global = max(max_min[i].second - pre.first, global);
pre = max_min[i];
}
}
return global;
}
};
No comments:
Post a Comment