vector 题目练习 算法代码分析 代码实现

 一. 数组中出现次数超过一半的数字

题目解析

给一个vector<int> 里面有一个数字出现次数超过了数组长度的一半 找到这个数返回 如果是奇数个数 例如11 那个出现次数最多的就至少出现6次  如果是偶数例如10 那么至少出现6次

算法分析

1.有一个数出现次数超过了一半  那么直接将里面的数排序之后 中间的数就一定是出现次数最多的那个数

代码里面用/2的方式来找中间的位置  如果是奇数个数 例如11 11/2=5  出现次数最多的就至少出现6次  那个下标5的位置是出现次数最多的 符合要求

 如果是偶数例如10 10/2=5   出现次数最多的数至少出现6次 下标5的位置符合要求

时间复杂度 排序O(N*logN) 然后就直接取中间数了  总时间复杂度O(N*logN)

2.整体的逻辑是 从左向右遍历 两个不同的数相互抵消  因为有一个数超过次数超过了一半 按照最坏的情况（每次出现次数最多的和一个其他的相互抵消）在遍历结束之后得到的结果也是出现次数最多的那个

这里代码实现的方式类似候选人 开始候选人为第一个位置的值 票数为1  从第一个位置开始和候选人比较

如果和候选人不同的话 自己就相当于抵消了候选人的一票  如果候选人票数为0了  候选人指向新的人(不是那个抵消了候选人一票的 是下一个位置的)

如果和候选人是一样的话  候选人票数++  那么下一次至少需要两个不同的人才能抵消  最后最后结束的候选人就是出现次数最多的

这样还是最坏的情况 有可以出现次数最多的在后面   前面其他的相互抵消 这样的话更能满足条件

时间复杂度O(N)

代码实现

1.

class Solution {public:int MoreThanHalfNum_Solution(vector<int>& numbers) {sort(numbers.begin(),numbers.end());return numbers[numbers.size()/2];}};

2.

class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {int con=1;int cur=numbers[0];int n=numbers.size();for(int i=1;i<n;++i){if(con==0){cur=numbers[i];con=1;}else if(numbers[i]!=cur){con--;}else{con++;}}    return cur;}
};

二.只出现一次的数字II

题目解析

题目描述很简单 给了一个vector<int> 里面有一个数出现了一次 其他都是出现了三次 要求找到出现一次的那个数

算法分析

1.暴力求解

除了只出现一次的那个数 其他的数都会有重复的 那么从第一个数开始遍历 看它前面的范围内后后面的范围内有没有和它相同的 数 有的话该值就不是要找的只出现一次的数  左右范围内都没有和该数相同的 那么该数就是要找的

时间复杂度 O（N^2）

2.将数转换成二进制来看 某一位上要么是1要么是0

那么对于出现三次的数  二进制的某一位上的值加起来的和要么是3要么是0 

其他的出现三次的数也是这样  那个将所有出现三次的数把他们二进制某一位上的值加起来 要么是0要么是3的倍数  再加上那个只出现一次数在该二进制位的值后要么不变(该位为0)  要么是3n+1 n>=0(该位为1) 

这样结果在%3之后的结果要么是0要么是1  取决于出现一次的数在该二进制位上的值   对二进制每一位都这样处理 每次得到的结果就是只出现一次数在该二进制位上的值  

如下图 出现三次的10 和只出现一次的12 在对二进制某一位加起来的值%3之后的结果和只出现一次的12的二进制该为上一模一样  在二进制每一位都加起来%3后最终结果就会12的一模一样

代码实现分析 

 int在32 位整数范围内  所以要把里面所有数二进制的每一位分别加起来

在最外围用一个for循环 进行32次 i从下标0开始

然后用范围for的方式遍历vector里面所有的数 让他们>>相应的位数之后和1进行按位与 的结果加起来（按位与是都为1才为1  数字1只有最后一位为1所以按位与后的结果其他位一定是0 最后一位是1还是0取决于与1按位与那个数的最后一位  而该数在>>相应位数之后才与1按位与操作的  也就是判断了>>前位数是1还是0)

然后根据%3的结果是1还是0做处理  如果是0说明只出现一次的数在该位上就是0不需要处理

如果是1要让最后s（这里让s作为最终返回的结果）该二进制位上也为1   让1左移相应位数后和s进行按位或的操作 (s刚开始是0 则每一位都是0 每次只对一位进行处理让这一位为1   不会影响其他位) 

对于从左开始的第一位 也就是符号位 (0代表正数 1代表负数 )按这个逻辑也能正常的进行 （只出现一次的数是正数 处理最高位和%3后的结果就是0  是负数 最高位和%3后的结果就是1 左移31为到最高位于s异或后最高位就是1）

时间复杂度O(N)

代码实现

1.暴力求解

class Solution {
public:int singleNumber(vector<int>& nums) {int n=nums.size();for(int i=0;i<n;i++){bool b=true;for(int j=0;j<i;j++){if(nums[j]==nums[i])b=false;}for(int k=i+1;k<n;k++){if(nums[k]==nums[i])b=false;}if(b==true)return nums[i];}return nums[0];;}
};

2.二进制方法

int singleNumber(vector<int>& nums)
{int s = 0;for (int i = 0; i < 32; ++i){int total = 0;for (int num : nums){total += ((num >> i) & 1);   //把数组中所有从右往左 二进制的第i位加起来}if (total % 3==1)              //是1就说明只出现一次的数在该二进制位上为1 {s |= (1 << i);            //1<<i变位了一个从右往左第i位上的值为1其他位都是0的数  然后异或和按位或 将s第i位变位了1 其他位不变}}return s;
}

三.只出现一次的数字III

题目解析

给了一个vector<int> 里面有两个元素出现一次  其他出现两次 找到只出现一次的那两个元素

算法分析

只出现一次的数字I的题目里面 是有一个数出现一次其他数出现两次 那么直接将所有数异或 最后的结果就是那个只出现一次的数   

这里有两个出现一次的数x1 x2  如果这里还用异或 那么所有数异或后的结果就是这x1和x2异或的结果

x1和x2异或后的结果二进制表示里面至少有一位为1 (如果都为0 说明每一个二进制位上二个数都相同 那这两个数就完全相同 与题目描述不符)   那么就说明该二进制位上x1和x2 一定一个是1 一个是0

那么我们就可以根据在该二进制位上是1还是0来把所有数给分为两组x1和x2一定是在两个不同的组中(对于那些出现两次的数 相同的数一定是分在一组里面的) 

这样对于每一个组里面其实就相当于只出现一次的数I的题目了  然后对于两个组分别把里面所有的数异或后得到的两个值就是最后要返回的结果

代码实现分析

先用范围for遍历把所有数异或后的结果存到c中 然后对于这个c右移i位后与1按位与的方式 找到从右开始第一个为1的位置 在这个过程由count来计算移动了几次才得到的

知道在哪一个二进制位来分组之后(就是根据count 看右移多少位) 再次范围for遍历 让每一个数右移count位后此时从右开始的第一位的结果就是划分的评判规则  然后根据和1进行按位与的结果据此划分数据到两个不同的vector中  然后对每一个vector进行按位与找到最后要返回的x1 x2

代码实现

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int c = 0; // 存所有数异或后的结果 也就是两个只出现一次的数异或后的结果for (int x : nums) {c ^= x; // 先用范围for把所有数异或的结果存到c中}// 从右开始 找到二进制表示的第一个不为0的位置int con = 0;for (int i = 0;; ++i) {if ((c >> i & 1) == 1)break;con++; // con是几 c从右往左二进制第一个为1的就是几 从0开始}// 根据i来将vector分为两类vector<int> v1, v2;for (int x : nums) {if ((x >> con & 1) == 1) {v1.push_back(x);} elsev2.push_back(x);}// 将两个vector分别将里面的所有数异或的结果存到x1 x2中int x1 = 0, x2 = 0;for (int x : v1) {x1 ^= x;}for (int x : v2) {x2 ^= x;}return {x1, x2};}
};

四.删除有序数组中的重复项

题目解析

给了一个vector<int>  这里非严格递增是说会有相同的数连续挨着 如果不看重复的话那么里面就是递增的  所以其实里面就是是从小到大排序好的

要求在原地删重复的元素让只保留一个 就不能开新的空间来存   要求删重后的结果还应该是有序的  最后只需返回只出现一次元素的个数     

最后只会检查前k(去重后的个数)个元素  据此和返回的size来判断最终结果是否正确

算法分析

1.让cur指向第一个位置  遍历所有的数 

如果cur指向位置的值和它的前一个位置的值相等 则说明cur位置的值已经有过了 直接删除cur位置的值后cur指向的就直接是下一个元素(erase里面会在删除之后把后面的值自动向左移位)

如果cur位置的值和前一个位置的值不同那就说明cur位置的值是一个新的值 cur++指向下一个位置  一直遍历结束 

在遍历结束之后 nums里面的每一个数都是不一样的数了 直接用size返回此时里面的个数

如果只看代码的话只遍历了一遍时间复杂度为（N）但是里面的erase在删除后自动移位时间复杂度是O（N） 所有整体的时间复杂度 O(N^2)

2. 虽然题目说着让删除 但是最后只会检查前k(去重后的个数)个元素 所以其实不用真的删掉

 cur开始指向第一个位置   i从第一个位置开始遍历 

i指向位置的值与前一个位置的值不相同的话cur指向的位置就更新为新的 然后cur++指向下一个位置 

如果指向的位置与前一个位置相同cur不动等待下一次判断不同的时候才更新   

这个过程将相当于i来遍历 找到一个新的值cur位置就更新

在遍历结束之后 cur指向的是待更新的位置 它前面的所有元素就是去重后只出现一次的值  cur刚好就是前面值的个数  直接返回cur

代码实现

1.

class Solution {
public:int removeDuplicates(vector<int>& nums) {int cur = 1;while (cur < nums.size()) {if (nums[cur-1] == nums[cur])nums.erase(nums.begin() + cur);else cur++;}return nums.size();}
};

2.

class Solution {
public:int removeDuplicates(vector<int>& nums) {int cur = 1;for(int i=1;i<nums.size();++i){if(nums[i]!=nums[i-1]){nums[cur++]=nums[i];}}return cur;}
};