C++从零开始的打怪升级之路(day18)

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料

那么开启正题

今天分享的是关于vector的题目

1.只出现一次的数字1

136. 只出现一次的数字

给你一个?非空?整数数组?nums?，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间

这题可以用的方法很多，比如数组计数，排序等，但是符合题目要求的最简单的方法就是位操作，两个相同的数字异或结果为0，0和x异或结果是x，根据以上特性，我们遍历一遍数组全异或一遍，题目就迎刃而解了

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

        return ret;
    }
};

这是ac代码

2.只出现一次的数字2

137. 只出现一次的数字 II

给你一个整数数组?nums?，除某个元素仅出现?一次?外，其余每个元素都恰出现?三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题

这题是上面题的升级版，同样的我们还是要在位上下功夫，但是按位异或肯定行不通了，我们得靠别的方法，比如计数，创建一个32大的数组，将数据遍历按位是否为1对数组进行++，最后数组内的数据都是3n和3n+1，这时让ret加上3n+1对应的位，就可以得到想要的答案了，当然这里的重复数字也可以是2，5，7...

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int a[32] = { 0 };
        int i = 0;
        int ret = 0;
        for (i = 0; i < nums.size(); i++)
        {
            int j = 0;
            for (j = 0; j < 32; j++)
            {
                if (nums[i] & (1 << j))
                {
                    a[j]++;
                }
            }
        }
        for (i = 0; i < 32; i++)
        {
            if ((a[i] - 1) % 3 == 0)
            {
                ret += (1 << i);
            }
        }

        return ret;
    }
};

这是ac代码

今天的博客就到这里了，后续内容明天分享,最近因为考试周原因不能更新太多内容,等考试周结束了再"快马加鞭"

新手第一次写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！！！