<Hard> Maximum Gap (LeetCode : C#)

https://leetcode.com/problems/maximum-gap/

📕 문제 설명

정수 배열이 주어질 때 정렬된 상태에서 연속한 두 값의 차이 중 가장 큰 값 반환하기

제한 : 시간 복잡도 O(N), 공간 복잡도 O(N)

• Input
  정수 배열 nums
• Output
  연속한 두 값의 차이 중 가장 큰 값

예제

풀이 1.

정렬 하고 연속한 값들에 대한 최대 갱신하는 식으로
(정렬이 O(NlogN) 이라서 다른 방식 찾아봐야할듯하다.)

public class Solution {
    public int MaximumGap(int[] nums) {
        Array.Sort(nums);
        int answer = 0;
        for (int i = 1; i < nums.Length; i++)
        {
            answer = Math.Max(answer, Math.Abs(nums[i -1] - nums[i]));
        }

        return answer;
    }
}

결과 1.

풀이 2.

Bucket Sort 사용해서 O(N)으로 한 풀이

public class Solution {
    public int MaximumGap(int[] nums) 
    {
        if (nums.Length <= 1)
        {
            return 0;
        }

        int minValue = nums[0];
        int maxValue = nums[0];
        foreach (int num in nums) // 최대 최소 찾기
        {
            if (num < minValue)
            {
                minValue = num;
            }
            if (num > maxValue)
            {
                maxValue = num;
            }
        }
		
        int bucketSize = Math.Max(1, (maxValue - minValue) / (nums.Length - 1));
        int numBuckets = (maxValue - minValue) / bucketSize + 1;
		// max gap이므로 각 버킷별 최대와 최소 담기
        int[] minBucket = new int[numBuckets];
        int[] maxBucket = new int[numBuckets];
        bool[] hasValue = new bool[numBuckets];
        foreach (int num in nums)
        {
            int bucketIndex = (num - minValue) / bucketSize;
            minBucket[bucketIndex] = hasValue[bucketIndex] ? Math.Min(minBucket[bucketIndex], num) : num;
            maxBucket[bucketIndex] = hasValue[bucketIndex] ? Math.Max(maxBucket[bucketIndex], num) : num;
            hasValue[bucketIndex] = true;
        }
		// 이전 bucket 최대와 현재 bucket최소와 비교
        int maxGap = 0;
        int prevMax = maxBucket[0];
        for (int i = 1; i < numBuckets; i++)
        {
            if (hasValue[i])
            {
                maxGap = Math.Max(maxGap, minBucket[i] - prevMax);
                prevMax = maxBucket[i];
            }
        }

        return maxGap;
    }
}

결과 2.