问题长度为 n 的非空整数数组，其中只有一个数字出现了1次，其他均出现2次，快速找到这个数字

解决问题前，先把问题简化为一个具体的问题：

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

分析

首先，暂不考虑时间和空间复杂度，这个问题的解决方案有几种？

解法一暴力破解

每次从数组中取一个数，记为cur，然后从剩下的数中查找，如果找不到，则cur即为要找的那个数。这种解法时间复杂度是 O( $n^2$ )，空间复杂度是O(1)。

解法二排序

将数组排序后，再进行相邻元素的比较。这种解法的时间复杂度和空间复杂度主要依赖于排序算法。

排序算法的时间和空间复杂度如下：

排序法	时间复杂度(平均)	时间复杂度(最坏)	空间复杂度	稳定度
冒泡	O( $n^2$ )	O( $n^2$ )	O(1)	稳定
选择	O( $n^2$ )	O( $n^2$ )	O(1)	不稳定
插入	O( $n^2$ )	O( $n^2$ )	O(1)	稳定
快速	O( $nlog_2n$ )	O( $n^2$ )	O( $nlog_2n$ )	不稳定
归并	O( $nlog_2n$ )	O( $nlog_2n$ )	O(n)	稳定
堆	O( $nlog_2n$ )	O( $nlog_2n$ )	O(1)	不稳定

解法三 HashMap

因为HashMap的key值是唯一的，因此将数组一次放入HasMap中，如果key值已经存在则重复，这种解法的时间复杂度和空间复杂度均为O(n)

解法四位运算

这个解法也是本次的重点解法。

Java中的位运算是使用较少的部分，但是针对一些特殊场景，位运算可以给出更好的解法。针对问题中的2个和1个，主要采用位异或(^)来解决这个问题，先提出一个概念：

甲 ^ 乙 = 丙丙 ^ 甲 = 乙

解析：

--------甲：12 -> 0000 0000 0000 1100乙：7 -> 0000 0000 0000 0111丙= 甲 ^ 乙 ：11-> 0000 0000 0000 1011--------丙：11-> 0000 0000 0000 1011甲：12 -> 0000 0000 0000 1100丙 ^ 甲 ：7-> 0000 0000 0000 0111 = 乙

即第二次甲会把丙中的第一次甲给抵消，还原到乙。则，当乙=0时，不断地对乙进行异或，留下来的数就是我们要找的数字。这种解法的时间复杂度为O(n)，空间复杂度为O(1)。

问题长度为 n 的非空整数数组，其中只有一个数字出现了奇数次，其他均出现偶数次，快速找到这个数字

分析

解决了第一个问题再来看这个问题，采用第四种解法可以轻松解决这个问题，偶数次的异或会相互抵消，奇数次的异或会留下我们要找的数字，这种解法的时间复杂度为O(n)，空间复杂度为O(1)。

问题长度为 n 的非空整数数组，其中有2个数字出现了1次，其他均出现2次，快速找到这m个数字

分析

采用暴力破解、HashMap也可以解决这个问题，这里主要分析采用快速排序，大佬也可以尝试采用位运算解法

解法一排序

public int[] singleNumber(int[] nums) {
           //1 快速排序：依次找到每个数的位置 冒泡排序：不断找到最小的数的位置        quickSort(nums,0,nums.length-1);        int[] result=new int[nums.length];        //2 比较        int i=0,j=0;        while(i
   
    i&nums[j]>temp)                    j--;                nums[i]=nums[j];                while(i
    
     <=temp)                    i++;                nums[j]=nums[i];            }            nums[i]=temp;            quickSort(nums,low,i-1);            quickSort(nums,i+1,high);        }    }

转载地址：http://ljebb.baihongyu.com/

你可能感兴趣的文章

目录

问题 长度为 n 的非空整数数组，其中只有一个数字出现了1次，其他均出现2次，快速找到这个数字

分析

解法一 暴力破解

解法二 排序

解法三 HashMap

解法四 位运算

问题 长度为 n 的非空整数数组，其中只有一个数字出现了奇数次，其他均出现偶数次，快速找到这个数字

分析

问题 长度为 n 的非空整数数组，其中有2个数字出现了1次，其他均出现2次，快速找到这m个数字

分析