(LeetCode OJ)Missing Number【268】

2019-08-28 18:15栏目:编程学习

(LeetCode OJ)Missing Number【268】

 

(LeetCode OJ) 35. Search Insert Position

268. Missing Number

My Submissions

Question

Total Accepted: 31740 Total Submissions: 83547 Difficulty: Medium

 

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?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

 

Subscribe to see which companies asked this question

Hide Tags

Array Math Bit Manipulation

Hide Similar Problems

(H) First Missing Positive (M) Single Number (H) Find the Duplicate Number

 

//思路首先:
//我真服了这个题,题意理解错了,我还以为是干嘛呢!
//后来才明白原来是随机从0到size()选取了一些数,其中有一个丢失了,草
//别人的算法:数学推出,0到size()的总和减去当前数组和sum

class Solution {
public:
    int missingNumber(vector& nums) {
        int sum = 0;  
        for(int num: nums)
            sum  = num;  
        int n = nums.size();  
        return (n * (n   1))/ 2 - sum;  
    }
};

OJ)Missing Number【268】 268. Missing Number My Submissions Question Total Accepted: 31740 Total Submissions: 83547 Difficulty: Medium Given an array containing n disti...

35. Search Insert Position

My SubmissionsQuestionTotal Accepted:94638Total Submissions:256951Difficulty:Medium

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Subscribeto see which companies asked this question

Hide Tags

ArrayBinary Search

Hide Similar Problems

(E) First Bad Version

 

分析:

二分查找要插入的职责

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int low=0,high=nums.size()-1;
        while(low<=high)
        {
            int mid=(low high)/2;
            if(nums[mid]target)
                high=mid-1;//要插入的位置一定在mid的左边
            if(nums[mid]==target)
                return mid;//找到了
        }
        return low;
    }
};

OJ) 35. Search Insert Position 35. Search Insert Position My Submissions Question Total Accepted:94638Total Submissions:256951Difficulty:Medium Given a sorted array and a...

版权声明:本文由威尼斯人app发布于编程学习,转载请注明出处:(LeetCode OJ)Missing Number【268】