重庆建工招标平台_无锡网络建站_现在最火的发帖平台_seo优化员

1、题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]

输出：1

2、初始思路

2.1 思路

二分法

2.2 代码

class Solution:def singleNumber(self, nums: List[int]) -> int:nums.sort()def search(l,r):if l >= r:return nums[l]mid = (l+r) // 2if mid % 2 == 1:mid -= 1if nums[mid] == nums[mid+1]:return search(mid+2, r)else:return search(l, r-1)return search(0, len(nums)-1)

3 优化算法

3.1 思路

由于题目中已经明确其他数字的数量均为2，因此可以使用步长为2的遍历方法进行遍历，但注意要先进行排序。

3.2 代码

class Solution:def singleNumber(self, nums: List[int]) -> int:nums.sort()for i in range(0,len(nums),2):if i == len(nums)-1 or nums[i] != nums[i+1]:return nums[i]