给定一个数组,和一个数值k,判断是否可以将数组分成k份
作者:
Zh1995
,
2019-10-09 08:21:13
,
所有人可见
,
阅读 666
public static LinkedList<LinkedList<Integer>> fun(int arr[],int k)
{
HashMap<Integer,Integer> map=new HashMap<>();//key是数组值,value是个数
LinkedList<LinkedList<Integer>> res=new LinkedList<>();
int sum=0;
for(int i=0;i<arr.length;i++)
{
sum+=arr[i];
int val=map.getOrDefault(arr[i],0)+1;
map.put(arr[i],val);
}
if(sum%k!=0)
return null;//不能整除的话必然不能分组
int target=sum/k;
for(int i=0;i<arr.length;i++)
{
LinkedList<Integer> list=new LinkedList<>();
if(arr[i]==target)
list.add(arr[i]);
else if(map.get(target-arr[i])>0)
{
list.add(arr[i]);
list.add(target-arr[i]);
//将使用完的个数减1
map.put(target-arr[i],map.get(target-arr[i])-1);
map.put(arr[i],map.get(arr[i])-1);
}
if(list.size()>0)
res.add(list);
}
return res;
}