LeetCode算法题-Single Number(Java实现

作者: 程序员小川 | 来源:发表于2018-11-18 08:43 被阅读2次

    这是悦乐书的第175次更新,第177篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第34题(顺位题号是136)。给定一个非空的整数数组,除了一个元素外,每个元素都会出现两次。 找到那个只出现了一次的元素。例如:

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

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

    本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

    02 第一种解法

    因为已经限定传入的数组不为空,所以此题不需要考虑特殊情况。

    在解这道题之前,我们先来了解下Java中的异或(^)运算,它的计算规则是转换为二进制数后,两边的对应位不同时,取1,否则取0。如果遇到负数,需要用负数的补码进行计算。

    当两个相同的数做异或运算时,他们运算后的结果是0。

    当0和一个非零的数进行异或运算时,运算结果是那个非零的数。

    此题中,重复的元素都是出现两次,只会有一个元素只出现一次,那么对所有的元素进行异或运算,最后得到的结果就是那个只出现了一次的元素。

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

    此解法的时间复杂度是O(n),看见复杂度是O(1)。

    03 第二种解法

    我们可以先对数组进行升序排序,排序后出现两次的元素肯定是相邻的元素,对此可以使用count记数和相邻元素比较的方法,来找出只出现了一次的元素。

    第一次循环,count为1,此时需要判断i+1是否等于数组长度或者当前元素不等于后一元素,如果满足,那么再判断此时的count是否等于1,如果等于1,那么当前元素就是那个只出现了一次的元素,否则count重置为0,然后继续循环。

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

    04 小结

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode算法题-Single Number(Java实现

        本文链接:https://www.haomeiwen.com/subject/xlvwfqtx.html