【手把手带你刷好题】—— 65.数组中数字出现的次数
大家好,我是安然无虞。每篇前言博客主页:安然无虞作者认证:2021年博客新星Top2咱的口号:🌹小比特,大梦想🌹作者请求:由于博主水平有限,难免会有错误和不准之处,我也非常渴望知道这些错误,恳请铁汁批评斧正。火爆专栏:蓝桥杯基础算法剖析欢迎加入:比特社区面试题:数组中数字出现的次数题目链接:数组中数字出现的次数题目描述:一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找
大家好,我是安然无虞。
每篇前言
博客主页:安然无虞
作者认证:2021年博客新星Top2
咱的口号:🌹小比特,大梦想🌹
作者请求:由于博主水平有限,难免会有错误和不准之处,我也非常渴望知道这些错误,恳请铁汁批评斧正。
火爆专栏:蓝桥杯基础算法剖析
欢迎加入:比特社区
面试题:数组中数字出现的次数
题目链接:数组中数字出现的次数
题目描述:
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
示例:
解题思路
首先,如果题目是这样的:一个数组nums里除某个数字之外,其他数字都出现了两次,请找出这个数字。
那么很简单,我们可以直接给出代码:
但是本题没有这么简单,方法还是那么个方法,不过需要我们多想一点。我们可以把数组分为两组进行异或,但是必须将这两个数分在不同的组里,而且相同的数字必须在同一组中,这样就可以知道是哪两个数字不同了。
但是难就难在,如何正确对这两个数字进行分组。
具体思路是这样的:
- 将数组中所有数进行异或, 保存异或结果;
- 找到异或结果中第一次出现1的位(任意出现1的位也可以);
- 按照找到的这个位进行分组即可
OK,思路就是这么个思路,具体请看代码。
代码执行
int* singleNumbers(int* nums, int numsSize, int* returnSize) { //思考:为什么这里我用的是calloc(),而不是malloc()? int* ret = (int*)calloc(2, sizeof(int));//注意,malloc()和calloc()的区别 *returnSize = 2; int n = 0;//将n和数组中所有元素相异或,异或结果放到n中 int i = 0; for(i = 0; i < numsSize; i++) { n ^= nums[i]; } //找异或结果n中第一次出现1的位 int count = 0; //注意运算符的优先级 while((n & 1 << count) == 0)//异或:相同为0,相异为1 { count++; } //按照第一次出现1的位置进行分组 for(i = 0; i < numsSize; i++) { if(nums[i] & 1 << count) ret[0] ^= nums[i]; else ret[1] ^= nums[i]; } return ret; }
完整代码:
三、遇见安然遇见你,不负代码不负卿。
码字不易,求个三连。
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)