Leetcode刷题java之136. 只出现一次的数字

今天药忘吃喽~ 2021-10-30 01:04 234阅读 0赞

执行结果：

通过

显示详情

执行用时 :24 ms, 在所有 Java 提交中击败了18.67%的用户

内存消耗 :45.5 MB, 在所有 Java 提交中击败了5.05%的用户

题目：

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

说明：

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

示例 1:

输入: \[2,2,1\]  
输出: 1  
示例 2:

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

思路：

利用一个hashmap来记录某一个数字出现的次数，如果次数为1的话，那么就是要找的数字了，当然我们也可以看出，这种方法虽然思路比较简单，但是运算时间却是很高。

代码：

class Solution {
        public int singleNumber(int[] nums) {
            Map<Integer,Integer> map=new HashMap<>();
            int result=0;
            for(int x:nums)
            {
                if(map.containsKey(x))
                {
                    map.put(x,2);
                }else
                {
                    map.put(x,1);
                }
            }
            for(int y:nums)
            {
                if(map.get(y)==1)
                {
                    result=y;
                    break;
                }
            }
            return result;
        }
    }

优化的方法：

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了99.85%的用户

内存消耗 :42.2 MB, 在所有 Java 提交中击败了26.72%的用户

思路：

采用异或的思想，相同数字的异或为0，最后单出来那个就是最后的结果

代码：

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