hymn

忽有故人心头过,回首山河已是秋。

  menu
132 文章
0 浏览
2 当前访客
ღゝ◡╹)ノ❤️

寻找缺失的整数

题目:

假设一个数组中有若干个正整数,范围是1~ 100,其中98个整数出现了偶数次,2个整数出现了奇数次,如何找到这两个数?

(如果数组中只有一个出现了奇数次,就直接可以异或运算,结果就是这个数)

image.png

image.png

import java.util.Arrays;

/**
 * @author: daixyhymn
 * @description:
 * @date: 2020/11/9 17:58
 */
public class FindLostNum {

  public static int[] findLostNum(int[] array){
    // 保存2个奇数整数
    int[] res = new int[2];
    // 第一次进行异或运算
    int xorRes = 0;
    for (int i = 0; i < array.length; i++) {
      xorRes ^= array[i];
    }

    if (xorRes == 0) return null;

    // 确定两个整数的不同位,一次来分组
    int separator = 1;
    while (0 == (xorRes & separator)) {
      separator <<= 1;
    }

    // 第二次分组进行异或运算
    for (int i = 0; i < array.length; i++) {
      if (0 == (array[i] & separator)) {
        res[0] ^= array[i];
      } else {
        res[1] ^= array[i];
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int[] arr = {2, 2, 3, 1, 4 ,4, 6, 6};

    System.out.println(Arrays.toString(findLostNum(arr)));
  }
}


标题:寻找缺失的整数
作者:hymn
地址:https://dxyhymn.com/articles/2020/11/09/1604916838360.html