LeetCode 솔루션

[5/28] 268. Missing Number

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.28 13:21

7,548 조회
2 댓글
0 추천
0 비추천
목록 게시글 쓰기

Easy

61032879Add to ListShare

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

#LeetCode, #Microsoft, #Amazon, #Facebook, #Adobe, #Apple, #Salesforce, #VMware, #Nvidia, #Array, #Hash Table, #Math, #Bit Manipulation, #Sorting

링크

https://leetcode.com/problems/missing-number/ 4682 회 연결

익명
작성일 2022.05.28 13:24

C++
Runtime: 30 ms, faster than 40.25% of C++ online submissions for Missing Number.
Memory Usage: 18 MB, less than 65.00% of C++ online submissions for Missing Number.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n;
        for (int i = 0; i < n; ++i) {
            res += i - nums[i];
        }
        return res;
    }
};

익명
작성일 2022.05.28 13:42

class Solution {
    public int missingNumber(int[] nums) {
        
        int result = nums[nums.length-1];
        int lumpSum = 0;
        for(int i : nums){
            lumpSum += i;
        }
        
        int length = nums.length;
        
        result = ((length * (length+1)) / 2) - lumpSum;
        
        return result;
        
    }
}