找出重复3遍的数字

文章目录

1. 1. 题目
2. 2. 解答１
3. 3. 代码１
4. 4. 解答２
5. 5. 代码２

题目

一组整型数中，有一个数字重复3遍，其它数字重复2遍，请找出这个重复3遍的数字。比如：[88, 459, 5262, 88, -17, 677, 88, 677, -17, 459, 5262], 结果为88。要求程序代码中额外申请的空间为O(1)，请给出一个平均时间复杂度不大于O(nlogn)的算法。请首先用文字阐述答题思路，然后用Java程序实现。(阿里　2016)

解答１

1. 两个相同的数异或（^）之后的值为０
2. 将所有的数异或起来就可以消去相同的两个数
3. 任意数和０异或都得到自身

代码１

public static int xorArray(int[] arr){
    int result = 0;
    for (int i : arr) {
        result ^= i;
    }
    return result;
}

测试用例如下：

@Test
public void testXorArray(){
    int[] arr = {88, 459, 5262, 88, -17, 677, 88, 677, -17, 459, 5262};
    assertEquals(88, xorArray(arr));
}

解答２

1. 参考快速排序partition方法，将小于选中的数全部放在左边，大于或等于选中的数则放在右边。其中如果选中的数有多个，则最后一个数也必须是该数
2. 如果小于当前数的个数是偶数，则待查找的数大于等于选中的数。如果最后一位数不等于选中的数，则表示选中的数只有一个，此时选中的数即为要查找的数；递归查找大于或等于选中的数（去掉两头的数）
3. 如果小于当前数的个数是偶数，则待查找的数小于选中的数，递归查找所有小于选中的数

4. 如果右边没有数字，即所有的数都小于选中的数，则该数即为要查找的数

   代码２

   交换数组中的两个数：

   public static void swap(int[] arr,int i,int j){
       if (i == j) {
           return;
       }
       arr[i] = arr[i] ^ arr[j];
       arr[j] = arr[i] ^ arr[j];
       arr[i] = arr[i] ^ arr[j];
   }

   放快速排序的分割算法，将小于选中的数全部放到该数左边，大于等于选中的数全部放到右边。需要注意处理等于的情况。

       public static int partition(int[] arr,int start,int end){
           assert(start<end);
           int selectIndex = rand.nextInt(end - start+1) + start;
   //      System.out.println(start+" "+ end + " " + selectIndex);
   //      int selectIndex = end;
           int selectValue = arr[selectIndex];
           swap(arr, selectIndex, end);
           int i = start;
           int j = end - 1;
           while(i < j){
               while (arr[i] <= selectValue && i < j) {
                   if (arr[i]==selectValue) {
                       swap(arr, i, end-1);
                       if (arr[i]==selectValue) {//防止死循环
                           break;
                       }
                   }else {
                       i++;
                   }
               }
               while (arr[j]>=selectValue && i < j) {
                   if (arr[j]==selectValue) {
                       swap(arr, j, end-1);
                   }
                   j--;
               }
               while (arr[i] < selectValue && i <= j) {
                   i++;
               }
               if (i < j) {
                   swap(arr, i, j);
               }
           }
           swap(arr, i, end);
           if (arr[end-1] ==  selectValue) {
               swap(arr, end-1, end);
           }
   //      printArray(arr);
           return i;
           
       }

   查找代码：

   public static int lookupNumber(int[] arr){
       return lookupNumber(arr, 0, arr.length -1);
   }
   
   public static int lookupNumber(int[] arr, int start, int end){
       if (start == end) {//只有一个数
           return arr[start];
       }
       int i = partition(arr, start, end);
       if (i == end || arr[i] !=  arr[end]) {//如果选中的数字只有一个或者右边没有数字，则返回
           return arr[i];
       }
       if (((i - start) & 1) == 0) {//小于当前数的个数是偶数，则有３个数的在右边
           return  lookupNumber(arr, i + 1, end - 1);
       }else {
           return lookupNumber(arr, start, i-1);
       }
   }

   测试用例如下：（@Repeat(40000)是指循环执行测试40000次，循环测试见如何运行一个测试用例多次）

       @Test
       @Repeat(40000)
       public void testLookup2(){
           int[] arr = {88, 459, 5262, 88, -17, 677, 88, 677, -17, 459, 5262};
           int i = lookupNumber(arr);
           assertEquals(88, i);
   //      System.out.println("t===========================t");
       }