题目:
有n堆石子堆,第i堆一共有a[i]个石子。 可以对任意一堆石子数量大于1的石子堆进行分裂操作,分裂成两堆新的石子数量都大于等于1的石子堆。需要通过分裂得到m堆石子,他想知道这m堆石子的最小值最大可以是多少?
方法一:暴力查找
要查找的最大的最小值在[1,min(a[i])]之间,因此只需要在这个区间内查找符合条件的值即可, 从后往前枚举min(a[i])到1之间的数字,假设每堆分成a[j]/i堆,累加堆数为sum(a[j]/i),如果sum<m,说明最小堆的值需要减小才可以分出更多的堆数;当堆数大于等于m,说明找到符合条件的值
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型
* @param m long长整型
* @param a int整型一维数组
* @return int整型
*/
public int solve (int n, long m, int[] a) {
// write code here
int min=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
min=Math.min(a[i],min);
}
int i;
for(i=min;i>=1;i--){//从后往前查找
int sum=0;
for(int j=0;j<a.length;j++){
sum+=(a[j]/i);
}
if(sum>=m)break;//找到第一个使得分的堆数大于等于m的值即为最大的最小值
}
return i;
}
}
复杂度:
- 时间复杂度:O(min(a[i])∗n),外层循环最差循环min(a[i])次,内层循环n次
- 空间复杂度:O(1),额外变量的空间复杂度为常数级
方法二:二分查找
思路:
显然,方法一中在[1,min(a[i])]之间查找最小值时间复杂度过高,可以采用二分查找算法, 左指针left置于1,右指针right置于min(a[i]),计算每堆平均分a[i]/mid堆时可以分得的堆数,因为每一大堆分成的每一小堆中的值已经按最小值mid计算,如果分得的堆数仍然小于m,则mid的值位于右区间,因此往右区间查找;否则,当堆数大于等于m时,mid可能为目标值也可能可以再增大一点堆数也不会改变,因此继续往左区间查找,直到left>right;此时返回应该返回使得left>right的mid值,所以返回left-1
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型
* @param m long长整型
* @param a int整型一维数组
* @return int整型
*/
public int solve (int n, long m, int[] a) {
// write code here
int min=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
min=Math.min(a[i],min);
}//最大的最小值在1到min(a[i])间查找
int left=1,right=min;
while(left<=right){
int mid=(left+right)>>1;
int sum=0;
for(int i=0;i<n;i++){
sum+=(a[i]/mid);//当最小值为mid时平均分的堆数
}
if(sum<m)right=mid-1;//堆数小于需要分的堆数,最小值往左边查找,增大堆数
else if(sum>=m){left=mid+1;}//堆数大于等于要分的堆数,最小值可能是mid也可能稍微大一点,因此往右边查找
}
return left-1;//要返回mid,因此需要减去1
}
}
复杂度:
- 时间复杂度:O(nlog2(min(a[i]))),二分查找的时间复杂度为O(log2(min(a[i])))
- 空间复杂度:O(1),额外变量的空间复杂度为常数级