LeetCode面试题53 – II. 0~n-1中缺失的数字

156 views

题目

解答

方案一

class Solution {
    public int missingNumber(int[] nums) {
        int[] arr = new int[nums.length + 1];

        for (int i = 0; i < nums.length; ++i) {
            arr[nums[i]] = 1;
        }

        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] == 0) {
                return i;
            }
        }

        return -1;
    }
}

方案二

class Solution {

    public boolean missingNumber(int[] nums, int target, int start, int end) {
        if (start > end) {
            return true;
        }

        int mid = (start + end) / 2;
        if (mid >= nums.length) {
            return true;
        }

        int value = nums[mid];
        if (value == target) {
            return false;
        }

        if (value < target) {
            return missingNumber(nums, target, mid + 1, end);
        } else {
            return missingNumber(nums, target, start, mid - 1);
        }

    }

    public int missingNumber(int[] nums) {
        for (int i = 0, length = nums.length + 1; i < length; ++i) {
            if (missingNumber(nums, i, 0, nums.length)) {
                return i;
            }
        }

        return -1;
    }
}

要点

方案一的时间复杂度和空间复杂度均为O(N),只利用的数据的唯一性和有限性。
方案二使用折半查找的方式来寻找缺失的数据,需要注意查找失败时的退出条件。

准备的用例,如下

@Before
public void before() {
    t = new Solution();
}

@Test
public void test001() {
    assertEquals(2, t.missingNumber(new int[] { 0, 1, 3 }));
}

@Test
public void test002() {
    assertEquals(8, t.missingNumber(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 9 }));
}

@Test
public void test003() {
    assertEquals(1, t.missingNumber(new int[] { 0 }));
}

@Test
public void test004() {
    assertEquals(0, t.missingNumber(new int[] { 1 }));
}


若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode面试题53 – II. 0~n-1中缺失的数字

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud