首页 > 其他 > 详细

LeetCode 268. Missing Number

时间:2018-04-19 23:37:35      阅读:210      评论:0      收藏:0      [点我收藏+]

question:

question:

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

Example 1

Input: [3,0,1]
Output: 2

Example 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

 

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

 

first try:

class Solution {
    public int missingNumber(int[] nums) {
        int[] slot = new int[nums.length+1];
        
        for(int i=0; i<nums.length; i++) {
            slot[nums[i]] = 1;
        }
        
        for(int i=0; i<slot.length; i++) {
            if(slot[i] == 0) {
                return i;
            }
        }
        
        return -1;
    }
}

 

result:

技术分享图片

 

second try:

 

class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0, sum2 = 0;
        
        for(int i=0; i<nums.length; i++) {
            sum += nums[i];
        }
        
        for(int i=0; i<=nums.length; i++) {
            sum2 += i;
        }
        
        return sum2-sum;
    }
}

 

result:

技术分享图片

 

conclusion:

 

数据集合的特点,使得常量空间复杂度成为可能。

LeetCode 268. Missing Number

原文:https://www.cnblogs.com/hzg1981/p/8886452.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!