leetcode [#268]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example:

Given nums = [0, 1, 3] return 2.

Note
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

---

解决方案

public class Solution {
    public int missingNumber(int[] nums) {
        int N = nums.length;
        if(N == 0) return 0;
        int result = 0;
        Arrays.sort(nums);
        if(nums[N-1] != N){
            result = N;
        } else if(nums[0] != 0){
            result =  0;
        } else {
            for(int i = 0; i < N-1; i++){
                if(nums[i+1] - nums[i] != 1){
                    result = i+1;
                    break;
                }
            }
        }
        return result;
    }
}

---

注意事项

1. 先考虑长度为0的特殊情况。
2. 将数组排序。
3. 考虑两端情况。
4. 遍历考虑中间情况。