[Codility] 第四課 MissingInteger

寫一個 function：

• int solution(int A[], int N);

給一個含有 N 個整數的陣列 A，返回最小的正整數 (必須大於 0) 且不含在 A 陣列裡面
舉例來說 A = [1, 3, 6, 4, 1, 2] ，則 function 應該要返回 5。

A = [1, 2, 3]，function 返回 4
A = [−1, −3]，function 返回 1

條件：

• N是一個 1 ~ 100,000 的整數
• 陣列 A 的每一個元素範圍 -1,000,000 ~ 1,000,000

複雜度：

• 最糟的時間複雜度為 O(N)
• 最糟的空間複雜度為 O(N) (不含 input 的參數)

Java 程式碼

// you can also use imports, for example:
// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        HashSet<Integer> list = new HashSet<Integer>();
        if(A.length == 0){
            return 1;
        }
        boolean isSmallerThanZero = true;
        
        for(int i =0;i<A.length;i++){
            if(A[i]>=0){
                isSmallerThanZero = false;
            }
            list.add(A[i]);
        }
        
        if(isSmallerThanZero){
            return 1;
        }
        
        for(int i = 1;i<Integer.MAX_VALUE;i++){
            if(!list.contains(i)){
                return i;
            }
        }
        
        return 1;
    }
}
        

分數共拿 100%，
任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想