累加出整个范围所有的数最少还需要几个数
作者：Grey
原文地址:
题目描述#
给定一个有序的正数数组 arr 和一个正数 aim ，如果可以自由选择 arr 中的数字，想累加得到
1~aim范围上所有的数，返回 arr 最少还缺几个数。
例如:
arr = {1,2,3,7}，aim = 15
想累加得到1~15范围上所有的数，arr 还缺 14 这个数，所以返回 1。
arr = {1,5,7}，aim = 15
想累加得到1~15范围上所有的数，arr 还缺 2 和 4，所以返回 2。
题目链接见：累加出整个范围所有的数最少还需要几个数
主要思路#
如果区间是1~1，可以组成的数是1;
如果区间是1~2，可以组成的数是1,2,3,即1~3。
如果区间是1~3，可以组成的数是1,2,3,4，5，即1~5。
……
依此类推
如果区间是1~n，可以组成的数是1,2……（2*n - 2）,（2*n - 1），即1~（2*n - 1）。
所以，如果数组已经可以组成1~range，但是还没有达到1~aim，数组需要增加一个数range+1，就可以让数组的可以组成范围扩大到2*range+1，不断这个过程，直到覆盖1~aim这个区间，这种做法是最经济的。
完整代码如下
import java.util.Arrays;
import java.util.Scanner;
/**
* @author Young
* @version 1.0
* @date 2021/1/25 0:06
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int aim = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
System.out.println(missing(arr, aim));
in.close();
}
// 如果要实现1~range所有目标，但整个目标还没有达到1~aim，你永远缺range+1，一定是最省且最经济的，补上range+1后，能达到的数是1~2*range+1
// 先将数组排序，依次考察如何最经济使用i位置的数
public static int missing(int[] arr, int aim) {
int miss = 0;
long range = 0;
Arrays.sort(arr);
for (int item : arr) {
while (item > range + 1) {
// 数组每次可以扩充的范围
range += (range + 1);
miss++;
if (range >= aim) {
return miss;
}
}
range += item;
if (range >= aim) {
return miss;
}
}
while (aim >= range + 1) {
range += range + 1;
miss++;
}
return miss;
}
}
代码说明
首先对数组进行排序的目的是找到连续的数组区间，这样才能判断扩散的范围，然后遍历数组，其中
while (item > range + 1) {
// 数组每次可以扩充的范围
range += (range + 1);
miss++;
if (range >= aim) {
return miss;
}
}
表示数组出现了断层，比如 item 之前的数可以组成的1~8，但是 item 值为 12，说明9~11无法被组成，此时，原数组需要补充一个 9（即：miss++），就可以将原数组的可组成范围扩大到1~17（即：range+=(range+1)）。
时间复杂度O(N*logN)，瓶颈主要是前面的排序的时间复杂度。
空间复杂度O(1)。