累加出整个范围所有的数最少还需要几个数

累加出整个范围所有的数最少还需要几个数

作者：Grey

原文地址:

博客园：累加出整个范围所有的数最少还需要几个数

CSDN：累加出整个范围所有的数最少还需要几个数

题目描述

给定一个有序的正数数组 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)。

更多

算法和数据结构笔记