LEETCODE 540. Single Element in a Sorted Array 解题思路分析

题目大意:

有序数组中的单一元素

给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=540

解题思路分析:

这道题的解题方式有很多,比如我们循环一遍数组,然后使用HashMap来记录每种数字出现的个数,最后查看数字个数为1的即是答案。不过题目要求我们使用O(1)的空间复杂度来解题,因此HashMap方式并不推荐。

另一种相对简单的解题方式是两两比较数组中的数字,因为数组已经升序排列好,因此,从首位开始每相邻的两个数字应该是相同的,当出现不相同的数字时,这两个数字中下标较小的一个即是结果。

我个人最为推荐的是使用位运算的方式来解本题,实际上本题是异或运算的经典使用场景。Leetcode的题库中也有类似的题目:LEETCODE 136. Single Number 解题思路分析,与本题的描述几乎完全一致。

回到本题,我们首先回顾一下异或的基本概念。相同两数的异或结果为0,而0和任何数的异或结果都是那个任意的数字。因此,本题中所有相同的数字之间的异或结果都是0,0与那个单一元素的异或结果即是那个单一元素,也是本题的解。由于异或运算是符合交换法的,也就是说数组中这些数字的异或执行顺序并不会影响最终结果,因此本题中给定的数组即使没有排序,也不会影响我们使用异或运算来解题。

实现代码:

public int singleNonDuplicate(int[] nums) {
    int res=0;
    for(int n : nums) res^=n;
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Element in a Sorted Array.

Memory Usage: 39.8 MB, less than 8.00% of Java online submissions for Single Element in a Sorted Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-540-single-element-in-a-sorted-array-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

邮箱地址不会被公开。