数组中只出现一次的数(其它数出现k次)
发布日期:2021-05-07 11:06:06 浏览次数:27 分类:精选文章

本文共 700 字,大约阅读时间需要 2 分钟。

题目描述

给定一个整型数组 arr 和一个整数 k(k>1)k(k>1)。已知 arrarr 中只有 1 个数出现一次,其他的数都出现 k 次。请返回只出现了 1 次的数。
示例1
输入 [5,4,1,1,5,1,5],3
返回值 4

题解:最初看题觉得很类似与之前的几道位运算题目,写了一波代码发现忽略了一个问题,这道题目针对的范围比较局限,只能针对其余数字出现3次来求解,如果出现是奇数次(比如大于3的奇数)该题目的解法需要变换了。

这道题是 和 这两道题目的综合版本。
将每个数字转化为二进制表示,对于二进制的每一位,如果每一位为1 的个数可以整除k,那么表示要求的结果中该位为0,反之该位为1。最外层循环表示的是该求解第几位上的1的个数,第0位表示二进制中的最低位,通过右移操作 和 与 操作求解所有数字在该位上为1的和,在还原要求解的数字时需要使用左移操作来还原,不管是余数为0还是余数为1。

class Solution {   public:    int foundOnceNumber(vector
& arr, int k) { // write code here int res=0; for(int i=0;i<32;i++) { int sum=0; for(auto x:arr) { sum+=x>>i&1; } res+=(sum%k)<
上一篇:leecode 796 旋转字符串
下一篇:leecode 143. 重排链表

发表评论

最新留言

表示我来过!
[***.240.166.169]2025年04月11日 04时14分25秒