快速找到整型数组中的特异数

喜欢ヅ旅行 2022-08-12 17:00 56阅读 0赞

解释： 特异数：在一个整型数组中仅出现一次的数。

在算法设计中常常要求找出一个长度为N的数组A中存在的“特异数”，根据算法要求，可以分为以下几类：

1、排序法：时间复杂度O(NlogN)，空间复杂度O(1)

算法思想：通过快速排序实现对于原数组A的排序，然后遍历数组，判断数组中元素与其前后元素是否相同，如果相同则继续遍历，否则返回该元素。

2、位操作：时间复杂度O(N)，空间复杂度O(1)

*2.1 非特异性数字出现次数为偶数：时间复杂度为O(N)*

**偶数个相同的整型数字“亦或”后为0，而奇数个整型数字“亦或”后为本身。**

算法思想：在算法设计过程中考虑使用“**亦或（^）**”运算。通过遍历数组A，将数组元素与前面元素的亦或结果进行亦或运算，遍历结束返回的结果即为数组中的特异数。

核心代码如下：

**int result = A\[0\];**

**for(int i=1; i<N; i++)**

**result = result ^ A\[i\];**

*2.2 非特异性数字出现次数为奇数：时间复杂度为O(32\*N)*

**当非特异性数字出现次数为奇数时，可以发现基本的位运算无法满足算法要求，但是可以通过统计所有元素二进制表示是对应位置出现的1的个数，对每位中1的个数求和，然后对k取余（其中k指非特异性数字出现的次数），然后将每位与0取“或（|）”运算得到最终结果。**

算法思想：首先定义一个长度为32的数组B，该数组每个元素对应原数组元素二进制表示的每位中1的个数，通过两层循环实现算法：外层循环i从0~31，对应数组B中的元素，内层循环遍历数组A，统计元素对应位置i出现1的次数，然后将B\[i\]对k取余，作为最终结果在该位置的数字，依次处理得到最终结果。

核心代码如下：

**int\[\] bitsNum = new int\[32\];**

**int result = 0;**

**for(int i=0; i<32; i++) \{**

**for(int j=0; j<N; j++) \{**

**bitsNum\[i\] += (A\[j\] >> i) & 1;**

**\}**

**result = result | ((bitsNum\[i\]%3)<<i);**

**\}**

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关在数组中找到第二大的数

题目在数组中找到第二大的数你可以假定至少有两个数字您在真实的面试中是否遇到过这个题？样例给出 \[1, 3, 2, 4\], 返回 3. 给出 \

Myth丶恋晨/ 2024年02月18日 20:24/ 0 赞/ 57 阅读

相关 java读入整型数组的方式

平时习惯用c++写算法题，毕竟有STL可以用且输入耗时少，最近有几个作业OJ题要用java，且需要自己写输入输出，原先不太熟悉java的输入输出方法，于是去整理了一下 ja

谁践踏了优雅/ 2022年12月28日 08:18/ 0 赞/ 137 阅读

相关整型数组字符数组指针数组思考

1）数组字符串指针（地址） include <stdio.h> include <stdlib.h> void main(void)

阳光穿透心脏的1/2处/ 2022年12月18日 02:58/ 0 赞/ 218 阅读

相关整型中long型

public class java5_4 { / @param args / public static voi

爱被打了一巴掌/ 2022年09月17日 14:25/ 0 赞/ 239 阅读

相关整型中int型

public class java5_3 { / @param args / public static voi

刺骨的言语ヽ痛彻心扉/ 2022年09月17日 14:25/ 0 赞/ 227 阅读

相关整型中short型

public class java5_2 { / @param args / public static voi

柔情只为你懂/ 2022年09月17日 14:25/ 0 赞/ 231 阅读

相关快速找到整型数组中的特异数

解释：特异数：在一个整型数组中仅出现一次的数。在算法设计中常常要求找出一个长度为N的数组A中存在的“特异数”，根据算法要求，可以分为以下几类： 1、

喜欢ヅ旅行/ 2022年08月12日 17:00/ 0 赞/ 57 阅读

相关整型数在做除法时整型和浮点型的转换

include<stdio.h> int main(int argc, const char argv[]) { //两个整数相除，得到

╰半夏微凉°/ 2022年08月06日 06:15/ 0 赞/ 227 阅读

相关整型数的最大值

整型数按照位数划分，可以分为8位、16位、32位、64位等。其表示的范围如下。 <table> <thead> <tr> <th>整型数</th>

阳光穿透心脏的1/2处/ 2022年05月31日 06:51/ 0 赞/ 281 阅读

相关在有序旋转数组中找到一个数

![这里写图片描述][70] //在有序旋转数组中找到一个数 public class FindNum{ public stati

我就是我/ 2022年05月27日 10:40/ 0 赞/ 221 阅读