2017年網易校招筆試程式設計題第二題

1、題目

未曾将題目抄下，大緻題意如下：

給定n個正整數組成的數列，找出取這n個正整數中的一部分數字求和所不能得到的最小數。

【輸入】第一行：一個正整數n，為數列整整數的個數

第二行：n個正整數（由空格隔開）

【輸出】取這n個正整數中的一部分數字求和所不能得到的最小數。

2、 舉例

【輸入】3

5 1 2

【輸出】4

3、 我的思路

先将數組進行從小到大排序，然後依次檢查數組中是否存在seed(1，2，3……)

(1) 如果存在與seed相等的數字，則seed加1，進入下一輪判斷；

(2) 如果不存在與seed相等的數字但存在大于seed的數字，則跳出循環，并判斷目前已經比較過的數字之和是否大于seed。如果大于，則已經比較過的這些數字肯定可以組合成seed，則seed加1進入下一輪判斷，否則，已經比較過的這些數字肯定不能組合成seed，該seed符合條件；

(3) 如果數組中不存在大于等于seed的數字，則判斷數組中所有數字之和是否大于seed。如果大于，那麼數組中數字肯定可以組合成seed，則seed加1進入下一輪判斷，否則，已經比較過的這些數字肯定不能組合成seed，該seed符合條件；

4、 實作如下：

以下實作通過所有測試用例。

import java.util.Arrays;
import java.util.Scanner;

public class Test2
{   
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] input = new int[n];            
            int sum = ;

            //把輸入的n個數存入數組
            for(int i =; i < n; i++)
            {
                int temp  = in.nextInt();  
                sum += temp;
                input[i] = temp;
            }            
            Arrays.sort(input);           
            int seed = ;           
            while(true)
            {
                int flag = ;               
                int sum2 = ;

                for(int k =; k < n; k++)
                {                   
                    if(input[k] == seed)
                    {
                        flag = ;
                        break;
                    }
                    if(input[k] > seed)
                    {
                        flag = ;
                        break;
                    }
                    sum2 += input[k];
                }

                if(flag ==  && seed > sum)
                {
                    System.out.println(seed);
                    break;
                }
                else if(flag == )
                {
                    seed ++;
                }
                else 
                {
                    if(sum2 < seed)
                    {
                        System.out.println(seed);
                        break;
                    }
                    seed ++;                    
                }
            }            
        }
    }
}
           

5、 考後反思

在寫這篇部落格的時候，我發現其實第3部分中的思路存在很多問題。

第3部分中第(3)種情況隻可能發生在數組為1，2……n時，是以此時可以直接斷定取這n個正整數中的一部分數字求和所不能得到的最小數是數組中所有數字之和加1，而不用再進行比較。

6、 修改後代碼

以下實作未進行所有用例的測試。

import java.util.Arrays;
import java.util.Scanner;

public class Test2
{   
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] input = new int[n];            
            int sum = ;

            //把輸入的n個數存入數組
            for(int i =; i < n; i++)
            {
                int temp  = in.nextInt();  
                sum += temp;
                input[i] = temp;
            }

            Arrays.sort(input);         
            int seed = ;           
            while(true)
            {
                int flag = ;               
                int sum2 = ;               
                for(int k =; k < n; k++)
                {                   
                    if(input[k] == seed)
                    {
                        flag = ;
                        break;
                    }
                    if(input[k] > seed)
                    {
                        flag = ;
                        break;
                    }
                    sum2 += input[k];
                }

                //可以之後斷定符合條件的值
                if(flag == )
                {
                    System.out.println(sum+);
                    break;
                }
                else if(flag == )
                {
                    seed ++;
                }
                else 
                {
                    if(sum2 < seed)
                    {
                        System.out.println(seed);
                        break;
                    }
                    seed ++;                    
                }
            }            
        }
    }
}
           

7、 總結

我在這裡所寫題目的解題思路，隻是抛磚引玉，肯定還有很多大神有更好的實作方式，望不吝賜教，不勝感激。