黑群晖的做网站文件,鑫灵锐做网站多少钱,我的南京网站,wordpress 数学插件DS相关题目
题目一#xff1a;消失的数字 拿到这道题目之后#xff0c;首先可以想到的一个解题方法就是#xff0c;我们可以先排序#xff0c;排完序之后#xff0c;这个数组其实就是一个有序的数组了#xff0c;那只用比较数组中的每一个元素和他对应的下标是不是相等的…DS相关题目
题目一消失的数字 拿到这道题目之后首先可以想到的一个解题方法就是我们可以先排序排完序之后这个数组其实就是一个有序的数组了那只用比较数组中的每一个元素和他对应的下标是不是相等的如果是相等的那么就说明对应的数字其实是存在的如果是不相等的那么就说明对应的数字其实就是不存在的了但是如果要排序的话使用sort方法就不符合题目中说的时间复杂度为O(n)了但是在leetcode上还是可以通过编译的代码如下
class Solution {
public:int missingNumber(vectorint nums) {int i0;sort(nums.begin(),nums.end());for(i0;inums.size();i){if(nums[i]i)continue;elsereturn i;}return i;}
};解决这道题目的第二个思路其实就是位运算里面的异或数组中有n个数在这n个数的后面添加从0到n的每个整数则添加了n1个整数共有2n1个整数在2n1个整数中消失的数字只在后面n1个整数中出现一次其余的数字在前 n个整数中即数组中和后面n1个整数中各出现一次即其余的数字都出现了两次。根据出现的次数的奇偶性可以使用按位异或运算得到消失的数字。0和任何数字异或都是那个数字本身。由于2n1个整数中消失的数字出现了一次其余的数字都出现了两次因此对上述 2n1个整数进行按位异或运算结果就是消失的数字
class Solution {
public:int missingNumber(vectorint nums) {int ret0;for(int i0;inums.size();i){ret^nums[i];}for(int i0;inums.size();i){ret^i;}return ret;}
};第三种思路就是进行两个数字的做差就可以求出来那个消失的数字
class Solution {
public:int missingNumber(vectorint nums) {int nnums.size(); int retret(1n)*n/2;;for(int i0;in;i){ret-nums[i];}return ret;}
};
