LeetCode-268-丟失的數字

語言: CN / TW / HK

丟失的數字

題目描述:給定一個包含 [0, n] 中 n 個數的陣列 nums ,找出 [0, n] 這個範圍內沒有出現在陣列中的那個數。

進階:

  • 你能否實現線性時間複雜度、僅使用額外常數空間的演算法解決此問題?

示例說明請見LeetCode官網。

來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/missing-number/
著作權歸領釦網路所有。商業轉載請聯絡官方授權,非商業轉載請註明出處。

解法一:陣列遍歷

首先,獲取數字的長度為n,根據根據公式n*(n+1)/2得到從0到n的數字相加之和為sum,由於nums陣列中只缺少一個數,所以遍歷陣列,將sum減去陣列中所有的元素,然後剩下的數字就是要返回的數。

public class LeetCode_268 {
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = n * (n + 1) / 2;
        for (int num : nums) {
            sum -= num;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println(missingNumber(nums));
    }
}

【每日寄語】 最清晰的腳印,總是印在最泥濘的路上。