[LeetCode] 164. Maximum Gap

轉自LeetCode

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

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.

<Solution>
第一種解法，就是先 sort，然後歷遍找答案

code 如下

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.empty() || nums.size() < 2) {
	return 0;
	}
	//>> O(NlogN)
	sort(nums.begin(), nums.end());
	int maxGap = INT_MIN;
	for(int i = 1; i < nums.size(); i++) {
	maxGap = max(maxGap, nums[i] - nums[i-1]);
	}
	return maxGap;
	}
	};

view raw findMaxGapInArray_1.cpp hosted with ❤ by GitHub

第二種解法，是利用到 bucket sort 的概念

想法如下

• 將數字分配到相對應的 bucket，並且記錄每個 bucket 裡面的最大最小值

• 最後只需要歷遍每個 bucket，記算 bucket[i+1].minValue - bucket[i].maxValue，來找到最大的 gap

• 這個解法的關鍵點在於 bucketSize = (maxNum - minNum) / (size - 1)，這個值會是 gap 的最小值

code 如下(參考資料)

	class Bucket {
	public:
	bool isUsed;
	int maxValue;
	int minValue;
	Bucket() : isUsed(false), maxValue(INT_MIN), minValue(INT_MAX) {}
	};
	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.empty() || nums.size() < 2) {
	return 0;
	}
	const int maxNum = *max_element(nums.begin(), nums.end());
	const int minNum = *min_element(nums.begin(), nums.end());
	const int bucketSize = max(1, (maxNum - minNum) / (static_cast<int>(nums.size()) - 1));
	const int bucketNums = (maxNum - minNum) / bucketSize + 1;
	vector<Bucket> buckets(bucketNums);
	//>> modified bucket sort
	for(const auto &n : nums) {
	int bucketIdx = (n - minNum) / bucketSize;
	buckets[bucketIdx].isUsed = true;
	buckets[bucketIdx].maxValue = max(buckets[bucketIdx].maxValue, n);
	buckets[bucketIdx].minValue = min(buckets[bucketIdx].minValue, n);
	}
	int maxGap = 0;
	int prvMax = minNum;
	for(const auto &b : buckets) {
	if(b.isUsed) {
	maxGap = max(maxGap, b.minValue - prvMax);
	prvMax = b.maxValue;
	}
	}
	return maxGap;
	}
	};

view raw findMaxGapInArray_2.cpp hosted with ❤ by GitHub