Find the odd int (6Kyu) - 图1

题目

  1. Given an array of integers, find the one that appears an odd number of times.
  2. There will always be only one integer that appears an odd number of times.

原题 给定一个整数数组，找出出现奇数次的整数。总是只有一个整数出现奇数次
input : new int[]{20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5}
output : 5

分析

对数组进行遍历，找到出现奇数次的整数。

我的解法

  1. import java.util.Arrays;
  2. public class FindOdd {
  3.   public static int findIt(int[] a) {
  4.     Arrays.sort(a);
  5.     for(int i = 0; i< a.length ;i++){
  6.       if(i == a.length-1){
  7.         return a[i];
  8.       }else if (a[i] != a[++i] ){
  9.         return a[--i];
  10.       }
  11.     }
  12.     return 0;
  13.   }
  14. }

参考解法

  1. public class FindOdd {
  2.   public static int findIt(int[] A) {
  3.     int xor = 0;
  4.     for (int i = 0; i < A.length; i++) {
  5.       xor ^= A[i];
  6.     }
  7.     return xor;
  8.   }
  9. }

提升

利用异或运算，相同的数字进行异或后等于0，0与任意数字进行异或运算都是该数字本身。