C++ 中求按位或等于 k 的最大子集

问题陈述

给定一个非负整数数组和一个整数 k，找到按位或等于 k 的最大长度子集。

示例

If given input array is = [1, 4, 2] and k = 3 then output is:
[1, 2]
The bitwise OR of 1 and 2 equals 3. It is not possible to obtain
a subset of length greater than 2.

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

算法

以下是按位或的属性：

0 OR 0 = 0
1 OR 0 = 1
1 OR 1 = 1

  • 对于 k 的二进制表示中所有位等于 0 的位置，结果子集中所有元素的二进制表示中对应的位置也必须为 0。

  • 另一方面，对于 k 中位等于 1 的位置，必须至少有一个元素在对应位置上为 1。其余元素在该位置可以是 0 或 1，这并不重要。

  • 因此，为了获得结果子集，遍历初始数组。在决定元素是否应该包含在结果子集中时，检查 k 的二进制表示中是否存在任何位置为 0 且该元素对应位置为 1 的情况。如果存在这样的位置，则忽略该元素，否则将其包含在结果子集中。

  • 如何确定 k 的二进制表示中是否存在某个位置为 0 且某个元素对应位置为 1 的情况？只需取 k 和该元素的按位或。如果它不等于 k，则存在这样的位置，并且必须忽略该元素。如果它们的按位或等于 k，则将当前元素包含在结果子集中。

  • 最后一步是确定是否存在至少一个元素在 k 对应位置为 1 的位置上为 1。

  • 只需计算结果子集的按位或。如果它等于 k，则这是最终答案。否则，不存在满足条件的子集。

示例

现场演示

#include <bits/stdc++.h>
using namespace std;
void getSubSet(int *arr, int n, int k){
   vector<int> v;
   for (int i = 0; i < n; i++) {
      if ((arr[i] | k) == k)
         v.push_back(arr[i]);
   }
   int ans = 0;
   for (int i = 0; i < v.size(); i++) {
      ans |= v[i];
   }
   if (ans != k) {
      cout << "Subset does not exist" << endl;
      return;
   }
   cout << "Result = ";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
   }
   cout << endl;
}
int main(){
   int arr[] = { 1, 4, 2 };
   int k = 3;
   int n = sizeof(arr) / sizeof(arr[0]);
   getSubSet(arr, n, k);
   return 0;
}

输出

编译并执行上述程序时，会生成以下输出：

Result = 1 2

更新于： 2020-02-27

386 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告