​LeetCode刷题实战136:只出现一次的数字

共 2718字,需浏览 6分钟

 ·

2020-12-30 17:05

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做只出现一次的数字,我们先来看题面:
https://leetcode-cn.com/problems/single-number/

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


Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

题意


给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?


样例

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

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


解题

https://www.cnblogs.com/zfLee/p/9330127.html

先找出题目中的重点要求:
  1、线性时间复杂度:要求我们的代码时间复杂度最高为O(n),不能有嵌套循环等。
  2、不使用额外空间:要求空间复杂度最高为O(1)。
除此之外,还有重要的信息:
除了某个元素只出现一次以外,其余每个元素均出现两次。
  这个条件非常关键,一开始自己审题不清楚没注意到均出现两次这个关键点,按照其他元素出现多次的情况处理了,这样导致思路受限很多。

开始解题:

方法一(比较法):
  思路:先对数组进行排序,然后对 nums[i] 和 nums[i + 1]进行比较,如相等,i += 2,继续下一组比较,直到取到不相等的一组。
  注意:首先这个数组的长度肯定是奇数(目标数字只出现一次,其他所有数字出现两次),所以如果上述步骤没有找到不相等的一组数,那么肯定是数组的最后一个数字是单独出现的。
public static int singleNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num = num ^ nums[i];
        }
        return num;
    }
 
方法二(去重法):
  思路:利用HashSet的特性,删除重复的数组元素,最后剩下一个单独的元素,返回即可。

public static int singleNumber(int[] nums) {
        Set set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) { // add成功返回true,如果set中已有相同数字,则add方法会返回false
                set.remove(nums[i]); // 删除重复出现的数字
            }
        }
        return set.iterator().next(); }

方法三(求差法):
  思路:先对数组排序,显而易见的,单独出现一次的数据必然是出现在数组下标为偶数的位置(下标从0开始),那么所有奇数下标的元素之和减去偶数下标的元素之和,就是需要求得的结果。
  代码如下:
public static int singleNumber(int[] nums) {
        int num = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 偶数下标位置 num += nums[i],奇数下标位置 num -= nums[i]
            num = i % 2 == 0 ? num + nums[i] : num - nums[i];
        }
        return num;
    }

方法四(异或法)
  思路:根据异或运算的特点,相同的数字经过异或运算后结果为0,除单独出现一次的数字外,其他数字都是出现两次的,那么这些数字经过异或运算后结果一定是0。而任何数字与0进行异或运算都是该数字本身。所以对数组所有元素进行异或运算,运算结果就是题目的答案。
  上代码:
public static int singleNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num = num ^ nums[i];
        }
        return num;
    }


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-120题汇总,希望对你有点帮助!
LeetCode刷题实战121:买卖股票的最佳时机
LeetCode刷题实战122:买卖股票的最佳时机 II
LeetCode刷题实战123:买卖股票的最佳时机 III
LeetCode刷题实战124:二叉树中的最大路径和
LeetCode刷题实战125:验证回文串
LeetCode刷题实战126:单词接龙 II
LeetCode刷题实战127:单词接龙
LeetCode刷题实战128:最长连续序列
LeetCode刷题实战129:求根到叶子节点数字之和
LeetCode刷题实战130:被围绕的区域
LeetCode刷题实战131:分割回文串
LeetCode刷题实战132:分割回文串 II
LeetCode刷题实战133:克隆图
LeetCode刷题实战134:加油站
LeetCode刷题实战135:分发糖果


浏览 15
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报