21xrx.com
2024-12-22 23:42:10 Sunday
登录
文章检索 我的文章 写文章
C++:寻找数组中只出现一次的两个数
2023-06-27 08:49:43 深夜i     --     --
C++ 数组 出现一次 两个数

在C++编程中,我们有时候需要寻找一个数组中只出现一次的两个数。这可能会让一些新手编程者感到困惑,但实际上,这个问题是可以用C++简单而有效的解决的。

我们可以通过使用异或运算来找出只出现一次的两个数。这种方法的原理是将整个数组中的数全部异或起来,得到的就是这两个只出现一次的数的异或结果。

接着,我们再通过一些位运算的方法,分离出这两个数。首先,我们需要找到这个结果的任意一位为1的位置。然后,我们根据这一位为0或1将所有数字分为两个组:一个组在这一位上为0,另一个组为1。这样两个只出现一次的数就被分在了不同的组中,然后我们分别将两个组内的数异或起来,即可得到这两个数。

下面是一段简单的代码,可用来解决上述问题:


void find_two_numbers(int arr[], int n)

{

  int res = 0;

  for (int i = 0; i < n; ++i)

  {

    res ^= arr[i];

  }

  int rightmost_1bit = res & -res;

  int num1 = 0, num2 = 0;

  for (int i = 0; i < n; ++i)

  {

    if (arr[i] & rightmost_1bit)

    {

      num1 ^= arr[i];

    }

    else

    {

      num2 ^= arr[i];

    }

  }

  std::cout << "The two numbers are: " << num1 << " and " << num2 << std::endl;

}

以上便是C++中寻找数组中只出现一次的两个数的方法。希望这篇文章对你有帮助!

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复