[随缘一题]排序数组中的单个元素

数据结构和算法►数组 , , 评论

前言

重磅!每日一题系列大改版了!

因为我发现每日一题太难了,,,总会出现一些加班已经很累了(懒得不想动)的时候,而且周末有事多做两道题都叫做同一天的每日一题也让我这个强迫症贼难受.

因此![每日一题]系列从今天开始变为[随缘一题]系列!

来源:

lintcode-排序数组中的单个元素

描述

给定一个排序数组，只包含整数，其中每个元素出现两次，除了一个出现一次的元素。 找到只出现一次的单个元素。

样例

1
2
输入：[1,1,2,3,3,4,4,8,8]
输出：2
1
2
输入：[3,3,7,7,10,11,11]
输出：10

解题思路

话说这道题在我校招的时候见过的,忘记在面哪个公司时现场问到了.

我当然是回答出来了粗暴的版本,比如:遍历计数.[Facepalm]

言归正传,这道题其实不算难题,可以通过很多暴躁的方法来解决,比如:

  1. 遍历计数. 遍历数组,对每个元素进行计数,之后返回只出现一次的元素.
  2. 逐个消除. 从index=0开始,与之后的每一个元素比较,如果遇到相同的,则将两个元素一起移除掉,如果遍历至结尾,还没有和当前元素相同的,则返回当前元素.

但是今天我不用这两个方法,使用位运算符来解决.

异或(^):

两个操作数的位中，相同则结果为0，不同则结果为1。

比如:7^6=1;怎么计算的呢?当然不是直接减法了!而是:

将7和6都转换为2进制进行计算.

1
2
3
4
7    = 1 1 1
6    = 1 1 0
---------
7^6  = 0 0 1 = 1

熟悉异或或者观察力强的胖友可能会发现异或的一些规律:

比如:

  1. 两个相同的数异或为0. 比如:7^7=0;
  2. 0和任何数异或结果为该数字. 比如:7^0=7;

知道这两条规律是不是就可以用在本题中了?

出现两次的数字异或之后都为0,拿到0和唯一出现一次的数字异或,结果就是所求的只出现一次的数字.

所以此题的机智的解法就是:对数组中的所有数字异或即可.

实现代码

1
2
3
4
5
6
7
8
public int singleNonDuplicate(int[] nums) {
  // write your code here
  int result = 0;
  for (int num : nums) {
    result = result ^ num;
  }
  return result;
}

完。




ChangeLog

2018-12-23 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。