leetcode-268-Missing Number

2019-11-11 05:15:38

字体：大中小

来源：转载

供稿：网友

问题

题目：[leetcode-268]

思路

主要是对空间的限制比较严格。想到的办法就是，反正就是数组嘛。也没什么别的方法，试试加起来看看，或者减一下试试。需要特别注意的是：[1,2,3]和[0,1,2]这种他们本生就是等差数列。要判断初始项是不是为0。

代码

class Solution {public: int missingNumber(vector<int>& nums) { int sz = nums.size(); if(1==sz){ if(nums[0]) return 0; else return 1; } int min = nums[0]; int max = nums[0]; int sum = nums[0]; for( int i = 1; i < sz; ++i ){ sum += nums[i]; if( nums[i] > max ) max = nums[i]; if( nums[i] < min ) min = nums[i]; } int expected = max*(max+1)/2;// 等差数列求和 if( expected - sum ) return expected-sum; else return (min)?0:max+1; }};

代码

看了看别人的方法[位运算实现]

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

上一篇：[BZOJ2199][Usaco2011 Jan][2-SAT]奶牛议会

下一篇：ToStringBuilder学习（一）