概要
难度:简单
类型:数组
题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
分析
第一种思路是暴力破解,即统计每个元素出现的次数,如果次数为1则为所求,但不符合题意。
第二种思路是如果该数只出现了一次,那么从头遍历到尾和从尾遍历到头的下标都是相等的,可以根据这种思路来求,但不符合题意。
第三种思路是利用异或操作。
如:
1^1=0
1^1^2=2
1^1^2^2=0
1^1^7^2^2=7
代码
第一种思路:
/**
* 求只出现一次的数字(算法一:计算出现次数)
* @param nums
* @return
*/
public int singleNumber(int[] nums) {
int count;
int temp;
for (int i = 0; i < nums.length; i++) {
temp=nums[i];
count=0;
for(int j=0;j<nums.length;j++){
if(temp==nums[j]){
count++;
}
}
if(count==1){
return nums[i];
}
}
return -1;
}
第二种思路:
/**
* 求只出现一次的数字(算法二:指针i和j下标相同)
* @param nums
* @return
*/
public int singleNumber(int[] nums){
for (int num : nums) {
int index = findIndexOf(nums, num);
int lastIndex = findLastIndexOf(nums, num);
if(index==lastIndex&&index!=-1&&lastIndex!=-1){
return nums[index];
}
}
return -1;
}
/**
* 从都遍历到尾,得到该数的下标
* @param nums 数组
* @param item 数
* @return 返回下标
*/
public int findIndexOf(int[] nums,int item){
for (int i = 0; i < nums.length; i++) {
if(nums[i]==item){
return i;
}
}
return -1;
}
/**
* 从尾遍历到头,得到该数的下标
* @param nums 数组
* @param item 数
* @return 返回下标
*/
public int findLastIndexOf(int[] nums,int item){
for(int i=nums.length-1;i>=0;i--){
if(nums[i]==item){
return i;
}
}
return -1;
}
第三种思路:
/**
* 求只出现一次的数字(算法三:异或操作)
* @param nums
* @return
*/
public int singleNumber(int[] nums){
int sum = nums[0];
for(int i = 1;i < nums.length;i++){
sum ^= nums[i];
}
return sum;
}