累加出整個範圍所有的數最少還需要幾個數

作者：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)。

更多

演演算法和資料結構筆記