程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode]Maximum Gap

[LeetCode]Maximum Gap

編輯:關於C++

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.

Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.

桶排序

public class Solution {
	class Pair{
		int min;
		int max;
		Pair(int min,int max){
			this.min = min;
			this.max = max;
		}
	}
    public int maximumGap(int[] num) {
    	if(num.length<=1) return 0;
    	int mn = num[0],mx = num[0];
    	int len = num.length;
    	for(int n:num){
    		mn = Math.min(mn, n);
    		mx = Math.max(mx, n);
    	}
    	if(mn== mx) return 0;
    	//桶間的間隔
    	int dist = (mx-mn)/len+1;
    	//每個pair就是一個桶,用來存儲映射到該桶的最大與最小數
    	Pair[]buck = new Pair[len];
    	for(int n:num){
    		//映射的桶下標
    		int index = (n-mn)/dist;
    		if(buck[index]==null) {
    			buck[index]= new Pair(n,n);
    			continue;
    		}
    		Pair p = buck[index];
    		p.min = Math.min(n,p.min);
    		p.max = Math.max(n,p.max);
    	}
    	int preMax = buck[0].max;
    	int res = preMax-buck[0].min;
    	for(int i=1;i





  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved