在3n + 1个数字中找到唯一的数字

Question

我在接受采访时被问到这个问题.

鉴于此,有3n + 1个数字.这些数字中的n个出现在三元组中,只有1个出现在单个时间内.我们如何在线性时间内找到唯一的数字,即O(n)？这些数字没有排序.

请注意,如果有2n + 1个数字,其中n个成对出现,我们可以对所有数字进行异或,以找到唯一的数字.面试官告诉我,这可以通过比特操纵来完成.

Answer 1

您可以发明一个3nary XOR(调用它XOR3)操作,它在base 3而不是base 2中运行,并且简单地将每个3nary数字模3(当通常XOR采用2nary digit modulo 2时).

然后,如果您使用XOR3所有数字(首先将它们转换为3nary),您将获得唯一的数字(在基数3中,因此您需要将其转换回来).

然而,复杂性并不完全是线性的,因为从/到基数3的转换需要额外的对数时间.但是,如果数字范围是常数,则转换时间也是恒定的.

关于C++的代码(故意冗长):

vector<int> to_base3(int num) {
  vector<int> base3;
  for (; num > 0; num /= 3) {
    base3.push_back(num % 3);
  }
  return base3;
}

int from_base3(const vector<int> &base3) {
  int num = 0;
  for (int i = 0, three = 1; i < base3.size(); ++i, three *= 3) {
    num += base3[i] * three;
  }
  return num;
}

int find_unique(const vector<int> &a) {
  vector<int> unique_base3(20, 0); // up to 3^20
  for (int num : a) {
    vector<int> num_base3 = to_base3(num);
    for (int i = 0; i < num_base3.size(); ++i) {
      unique_base3[i] = (unique_base3[i] + num_base3[i]) % 3;
    }
  }

  int unique_num = from_base3(unique_base3);
  return unique_num;
}

int main() {
  vector<int> rands { 1287318, 172381, 5144, 566546, 7123 };
  vector<int> a;
  for (int r : rands) {
    for (int i = 0; i < 3; ++i) {
      a.push_back(r);
    }
  }
  a.push_back(13371337); // unique number

  random_shuffle(a.begin(), a.end());

  int unique_num = find_unique(a);
  cout << unique_num << endl;
}

Answer 2

1. 计算每组在3n + 1个数字中出现的次数.
2. 减少每个位数模3.
3. 剩下的是单个数字的位模式.

哦,dreamzor(上图)打败了我.