首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leecode刷题(5)-- 只出现一次的数字

leecode刷题(5)-- 只出现一次的数字

作者头像
希希里之海
发布2019-01-03 15:56:12
4610
发布2019-01-03 15:56:12
举报
文章被收录于专栏:weixuqin 的专栏weixuqin 的专栏

leecode刷题(5)-- 只出现一次的数字

只出现一次的数字

描述:

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

说明:

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

示例:

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

思路:

因为“除了某个元素只出现一次一次,其余每个元素均出现两个”,所以如果该数组有序,且有一个元素只出现一次,以步数2向后遍历,那么一定会存在a[i] != a[i+1]。所以我们可以将数组排序,然后隔两个元素比较一次,看相邻元素的值是否相等,若不相等,即为我们要找得出现一次的数字。

因为我们这里用到了排序,排序的时间复杂度为 O(nlogn),不是线性时间复杂度 O(n),其实并不是很好。

代码如下:

import java.util.Arrays;

public class SingleNumber {
    public int singleNumber(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i += 2) {
            if (i == nums.length - 1) {
                return nums[i];
            }
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,4,3,3};
        SingleNumber singleNumber = new SingleNumber();
        int a = singleNumber.singleNumber(nums);
        System.out.println(a);
    }
}

改进:

我们可以使用异或的方法,便能很完美的解决这个问题。

所谓异或,即为:参与运算的两个元素,两者的值不同返回true,两者的值相同返回false。

通过学习计算机基础,我们知道异或表达式有几个规律:

  1. 恒定律:A ^ 0 = A
  2. 归零率:A ^ A = 0
  3. 交换律:A ^ B = B ^ A
  4. 结合律:(A ^ B) ^ C = A ^ (B ^ C)

这里我们举个例子:

比如我们的数组为:{2,3,2,3,1}

我们使用异或运算:

  2^3^2^3^1
= 2^2^3^3^1
= 0^0^1
= 1

所以看到这里,大家是不是懂了,我们让数组中的元素做异或运算,结果便为要找的 ”只出现一次的数字“。

代码如下:

import java.util.Arrays;

public class SingleNumber {
    public int singleNumber(int[] nums){
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int result = 0;
        for (int i =0; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,4,3,3};
        SingleNumber singleNumber = new SingleNumber();
        int a = singleNumber.singleNumber(nums);
        System.out.println(a);
    }
}

可以看到,时间复杂度为 O(n),符合题目线性时间复杂度的要求。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-12-28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • leecode刷题(5)-- 只出现一次的数字
    • 只出现一次的数字
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档