82. Single Number [easy]
2024-08-21 02:12:07
Description
Given 2*n + 1 numbers, every numbers occurs twice except one, find it.
Example
Given [1,2,2,1,3,4,3], return 4
刷题中，遇到一个比较有趣的题目，记录一下。
题目给了2*n+1个数，其中有n组数成双出现，只有一只单身贵族。那么如何找到这个数呢？一开始想了一个比较笨的方法，先将数组排序，看连续出现的两个数是否一样，不一样的就是要找的那个。
方法一：
public class Solution {
/**
* @param A: An integer array
* @return: An integer
*/
public int singleNumber(int[] A) {
// write your code here
Arrays.sort(A);
if(A.length==1){
return A[0];
}
for(int i=0;i<A.length;i+=2){ //注意i迭代数为2
if(i==A.length-1)
return A[i]; //如果是最后一个，直接返回该值
if(A[i]!=A[i+1])
return A[i];
}
return 0;
}
}
方法二：
在网上找到的一种更巧妙的方法，利用“异或”运算的一个性质：（1）一个数与另外两个相同的数异或之后，还等于这个数（2）异或运算的可交换性
例如： 2 XOR 1=3 3 XOR 1=2 也可以描述为 2 XOR (1 XOR 1)=2 XOR 0=2.
对于本题来说，把所有数XOR得到的结果就是那只“单身贵族”：
public class Solution {
/**
* @param A: An integer array
* @return: An integer
*/
public int singleNumber(int[] A) {
//根据题目的意思，A数组中至少有一个数
int res=A[0];
for(int i=1;i<A.length;i++){
res^=A[i];
}
return res;
}
}
最新文章
- ABP总体介绍
- openresty 前端开发入门三之JSON篇
- App的启动过程
- python窗体——pyqt初体验
- nmap 高级扫描用法
- linux代码段，数据段，BSS段, 堆，栈（二）
- linux-网卡故障
- nyoj 69 数的长度
- poj 2739 Sum of Consecutive Prime Numbers 小结
- perl 读取Excel写入txt 乱码
- Java 包与类的命名（util、service、tool、dao ）区别
- openvpn 客户端配置
- vue中 用媒体查询 空置根节点字体大小
- JAVA 文件与base64之间的转化, 以及Web实现base64上传文件
- 常用C字符串函数
- oracle卸载清除注册表(彻底卸载)
- DataGridView使用技巧十三：点击列头实现升序和降序排序
- [Android] 开发第九天
- OA与ERP集成 可行？
- 关于mysql中[Err] 1451 -Cannot delete or update a parent row: a foreign key constraint fails