DS相关题目

题目一：消失的数字

• 拿到这道题目之后，首先可以想到的一个解题方法就是，我们可以先排序，排完序之后，这个数组其实就是一个有序的数组了，那只用比较数组中的每一个元素和他对应的下标是不是相等的，如果是相等的，那么就说明对应的数字其实是存在的，如果是不相等的，那么就说明对应的数字其实就是不存在的了，但是如果要排序的话，使用sort方法就不符合题目中说的时间复杂度为O(n)了，但是在leetcode上还是可以通过编译的，代码如下

class Solution {
public:int missingNumber(vector<int>& nums) {int i=0;sort(nums.begin(),nums.end());for(i=0;i<nums.size();i++){if(nums[i]==i)continue;elsereturn i;}return i;}
};

• 解决这道题目的第二个思路其实就是位运算里面的异或，数组中有n个数，在这n个数的后面添加从0到n的每个整数，则添加了n+1个整数，共有2n+1个整数，在2n+1个整数中，消失的数字只在后面n+1个整数中出现一次，其余的数字在前 n个整数中（即数组中）和后面n+1个整数中各出现一次，即其余的数字都出现了两次。根据出现的次数的奇偶性，可以使用按位异或运算得到消失的数字。0和任何数字异或都是那个数字本身。由于2n+1个整数中，消失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+1个整数进行按位异或运算，结果就是消失的数字

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

• 第三种思路就是进行两个数字的做差，就可以求出来那个消失的数字

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