164. Maximum Gap
这道题用到的是桶排序的思路：
桶排序工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
对于本题来说：
首先对数组进行桶排序，然后找出最大的gap。
首先明确，最大的gap肯定是后桶的最小值减去前桶的最大值，注意此处说的桶均为有效桶，即不包括空桶。
因此无需进行桶内排序，仅需记录每个有效桶的最大值和最小值即可。
为何最大的gap肯定是后桶的最小值减去前桶的最大值？
假设有数组x[1...n]，其中最大的元素为max，最小元素为min，将左闭右开的实数区间[min，max)划分为n-1个等长的子区间（桶），每个子区间也是左闭右开的，我们用len来表示每个子区间的长度。除去max和min(因为max肯定在最后一个桶，min肯定在第一个桶），剩下的n-2个数，每个数都属于其中一个桶。对于同一个桶的两个数，因为桶是左闭右开的，所以他们的距离肯定是小于len的。然后，关键的一点是，n-2个数放进n-1个桶，由抽屉原理可以知道，肯定有一个桶是空的，所以，距离最远的相邻的两个数，肯定是属于两个不同的桶。于是，我们可以把每个桶都扫描一次，相邻最远的两个数，必定其中一个是某个桶里的最大值，另一个是另一个桶里的最小值。
public class Solution {
public int maximumGap(int[] num) {
if(num == null || num.length<2){
return 0;
}
int maxval = Integer.MIN_VALUE;
int minval = Integer.MAX_VALUE;
//求解数组最值
for(int i=0; i<num.length; i++){
if(num[i]>maxval) maxval = num[i];
if(num[i]<minval) minval = num[i];
}
//数组内的元素值相同
if(minval==maxval){
return 0;
}
//数组仅有两个元素
if(num.length==2){
return maxval-minval;
}
int len = (int)Math.ceil((double)(maxval-minval)/(num.length-1)); //求解桶间差值,向上取整
int n = (maxval-minval)/len;
int maxBuk[] = new int[n+1];
int minBuk[] = new int[n+1];
Arrays.fill(maxBuk,Integer.MIN_VALUE);
Arrays.fill(minBuk,Integer.MAX_VALUE);
//桶映射
for(int val:num){
int temp = (val-minval)/len;
maxBuk[temp] = Math.max(val,maxBuk[temp]);
minBuk[temp] = Math.min(val,minBuk[temp]);
}
//求解最大gap,最大差值位于后桶的min-前桶的max
int gap = 0;
int pre = maxBuk[0];
for(int i=1; i<=n; i++){
if(maxBuk[i]==Integer.MIN_VALUE && minBuk[i]==Integer.MAX_VALUE){ //忽略空桶
continue;
}
gap = Math.max(gap,minBuk[i]-pre);
pre = maxBuk[i];
}
return gap;
}
}
167. Two Sum II - Input array is sorted
两个指针，这里有个坑，返回的索引不是从0开始的，而是从1开始的。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] res = new int[2];
if(numbers==null || numbers.length < 2 )
return res;
int left = 0;
int right = numbers.length - 1;
while(left < right){
if(numbers[left] + numbers[right] == target){
res[0] = left+1;
res[1] = right+1;
return res;
}
else if(numbers[left] + numbers[right] > target)
right --;
else
left ++;
}
return res;
}
}
168. Excel Sheet Column Title
注意这里先把n自减1，然后再进行除和余操作就可以啦。
class Solution {
public String convertToTitle(int n) {
StringBuilder str = new StringBuilder();
while(n>0){
n--;
str.insert(0,(char)('A' + n % 26));
n /= 26;
}
return str.toString();
}
}
169. Majority Element
既然有的元素出现次数超过一半，那么该元素出现次数的count和其他元素出现次数的count相互抵消后一定是正的，那么就进行计数就可以啦。
class Solution {
public int majorityElement(int[] nums) {
if(nums==null || nums.length==0)
return 0;
int maxNum = nums[0];
int count = 1;
for(int i =1;i<nums.length;i++){
if(nums[i]==maxNum)
count++;
else if(count>0)
count--;
else{
count = 1;
maxNum = nums[I];
}
}
return maxNum;
}
}
