Plain's Blog

休想打败我的生活🔥

LeetCode之只出现一次的数字(SingleNumber)

Plain's Avatar 2019-01-01 LeetCode

  1. 1. 题目描述
  2. 2. 要求
  3. 3. 示例
  4. 4. 实现
  5. 5. 总结

题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

要求

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

示例

1
2
Input: [2,2,1]
Output: 1

1
2
Input: [4,1,2,1,2]
Output: 4

实现

1
2
3
4
5
6
7
8
9
10
public static int singleNumber(int[] nums) {

int sum = 0;

for (int num : nums) {
sum ^= num;
}

return sum;
}

总结

采用了异或运算,零和任何数异或都等于任何数, 一个数异或两次就等于0。因为本题中除一个之外每个元素都出现两次,所以用循环异或所有数就等于,只出现一次的那个数。

本文作者 : Plain
This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接 : https://plain-dev.com/leetcode-singleNumber/

本文最后更新于 天前,文中所描述的信息可能已发生改变