C/C++教程

leetcode--找出数组中只出现一次的数字(位运算、set、常规解法)

本文主要是介绍leetcode--找出数组中只出现一次的数字(位运算、set、常规解法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:找出只出现一次的数字

要求:

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

说明:

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

解法1(位运算--推荐):

 public int singleNumber(int[] nums) {
        //1、使用异或解法,a^a = 0,a^a^b = a^b^a = b,a^0=a(速度最快1ms(100%\35.21%))
        int sum = 0;
         for(int i=0;i<nums.length;i++){
             sum ^= nums[i];
         }
        return sum;

      
}

解法2(使用set筛选):

 public int singleNumber(int[] nums) {

        //2、使用set,添加失败,说明该元素重复,去除元素
        HashSet hashSet = new HashSet();
         for(int o :nums){
             if(!hashSet.add(o)){
                 hashSet.remove(o);
             }
         }
         return (int)hashSet.toArray()[0];
}

解法3(寻找一般规律):

 public int singleNumber(int[] nums) {
      
        //3、直接判断的做法 (1)在第一个元素:1,2,2,4,4(2)2 2 3 4 4
        给数组排序后,目标总是index 为偶数,且index + 1 != index,
        Arrays.sort(nums);
        for(int i=0;i<nums.length -1;i = i+2){
            if(nums[i+1] != nums[i]){
                return nums[i];
            }
        }
        return nums[nums.length -1];
    }
}

涉及数组的寻找个别重复的数、非重复的数,总是可以考虑set的解法,常用的set方法:toArray()--转数组,add()、remove()方法

 

这篇关于leetcode--找出数组中只出现一次的数字(位运算、set、常规解法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!