C++LeetCode 구현(164.최대 간격 구하 기)

[LeetCode]164.Maximum Gap 최대 간격 구하 기
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Example 1:
Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
(3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
Note:

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Try to solve it in linear time/space.

이런 문제 에 부 딪 히 면 반드시 먼저 생각 한 것 은 배열 에 정렬 해 야 한 다 는 것 이다.그러나 문 제 는 선형 시간 과 공간 을 요구 하기 때문에 통 으로 정렬 하거나 기본 으로 정렬 할 수 밖 에 없다.여기 서 통 으로 Bucket Sort 를 정렬 합 니 다.먼저 배열 의 최대 치 와 최소 치 를 찾 은 다음 에 각 통 의 용량 을 확인 해 야 합 니 다.즉,(최대 치-최소 치)/개 수+1 입 니 다.통 의 개 수 를 확인 하 는 것 은(최대 치-최소 치)/통 의 용량+1 입 니 다.그리고 각 통 에서 국부 최대 치 와 최소 치 를 찾 아야 합 니 다.그리고 최대 간격의 두 개 수 는 같은 통 에 있 지 않 고 한 통 의 최소 치 와 다른 통 의 최대 치 사이 의 간격 이다.이것 은 모든 숫자 가 한 통 에 붐 비 는 것 이 아니 라 모든 통 에 평균 적 으로 분배 되 어야 하기 때문이다.이렇게 해서 최대 치 와 최소 치 는 반드시 같은 통 에 있 지 않 고 구체 적 으로 블 로 거들 도 할 수 없다 는 것 을 증명 한다.다만 이렇게 생각 하 는 것 이 매우 일리 가 있다 고 생각 합 니 다.여러분,관리 님 들 이 어떻게 증명 하 는 지 알 고 있다 면 블 로 거들 에 게 메 시 지 를 남 겨 주세요.코드 는 다음 과 같 습 니 다.

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() <= 1) return 0;
        int mx = INT_MIN, mn = INT_MAX, n = nums.size(), pre = 0, res = 0;
        for (int num : nums) {
            mx = max(mx, num);
            mn = min(mn, num);
        }
        int size = (mx - mn) / n + 1, cnt = (mx - mn) / size + 1;
        vector<int> bucket_min(cnt, INT_MAX), bucket_max(cnt, INT_MIN);
        for (int num : nums) {
            int idx = (num - mn) / size;
            bucket_min[idx] = min(bucket_min[idx], num);
            bucket_max[idx] = max(bucket_max[idx], num);
        }
        for (int i = 1; i < cnt; ++i) {
            if (bucket_min[i] == INT_MAX || bucket_max[i] == INT_MIN) continue;
            res = max(res, bucket_min[i] - bucket_max[pre]);
            pre = i;
        }
        return res;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/164  
참고 자료:
https://leetcode.com/problems/maximum-gap
http://blog.csdn.net/u011345136/article/details/41963051
https://leetcode.com/problems/maximum-gap/discuss/50642/radix-sort-solution-in-java-with-explanation
https://leetcode.com/problems/maximum-gap/discuss/50643/bucket-sort-java-solution-with-explanation-on-time-and-space
C++구현 LeetCode(164.최대 간격 구 함)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 구 최대 간격 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!