时间戳

首页 > 解决方案 > 具有二元与等于 0 的整数对

c++ - 具有二元与等于 0 的整数对

问题描述

两个整数 x 和 y 形成一个神奇对，如果它们的位与结果等于 0。给定一个整数数组，找出每个数组元素是否与其他数组元素形成一个神奇对。

输入

输入的第一行包含一个整数 T，表示测试用例的数量。每个测试用例的第一行都有一个整数 N，表示给定数组中的元素数。第二行包含 N 个以空格分隔的整数 a1,a2,...an 表示给定数组的元素。

输出

对于每个测试用例，在一行中打印 N 个空格分隔的整数。如果 ai 与给定数组的任何其他元素形成一个神奇的对，那么 ans'i 应该等于 1。否则 ans'i 是 0。

约束

1<=N,Ai<=10^6

我试过蛮力。对于每个元素，我检查了该数字的按位与是否为零与数组中存在的任何其他元素。显然，它的时间复杂度为 O(N^2)，而且我的大多数测试用例都超时了

这个问题在这里：https ://www.hackerearth.com/challenges/test/netapp-codenet-2017/algorithm/d2d1f6a92c6740278682e88ed42068a4/

任何人都可以建议我更好的方法或算法，以便通过时间限制吗？

蛮力代码：

int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
    cin >> a[i];
int ans[n];
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (a[i] & a[j] == 0)
            ans[i] = 1;
for (int i = 0; i < n; i++)
    cout << ans[i] << " ";

标签： c++algorithmbit-manipulationtime-complexity

解决方案

一种方法是为所有数字创建一个二叉树，如 Trie。

例如，如果你有数组 3 6 2 9 10，二进制数组看起来像

arr = 11, 110, 10, 1001, 1010，树会喜欢

                                     root
                                /             \
                               0               1
                                 \           /   \ 
                                  1         0     1
                                 / \       / 
                                0   1     0   
                                 \         \   
                                  1         1

如果我们遍历二进制数组中的每个元素，匹配条件的数字（答案）对于元素中的每个设置位应该为 0，对于元素中的未设置位应该为 0 或 1。

现在，我们只需要将这些位遍历到树中。如果我们能够做到，那么至少存在一个满足条件的数。

时间复杂度 O(N)。原因：- 有 n 个数字。每个数字都是 32 位二进制长度。创建新节点将花费 O(1)。因此，O(32N) => O(N)。inv_arr 的时间相同。

注意：尝试将数字转换为 32 位二进制数，因为它将涵盖范围内指定的所有数字。否则会出问题。这里 6 和 9 形成了一个神奇的对，但是 inv_arr 中的 0110 不能被遍历，并且将导致不存在神奇的对，因为无法遍历最左边的 0。如果所有数字都用相同长度的二进制表示，则树遍历将给出正确答案。

代码

public class BinaryNode {

    char c;
    public BinaryNode left;
    public BinaryNode right;

    public BinaryNode(char c) {
        this.c = c;
    }

}

public class BinaryTree {

    public BinaryNode root;

    public BinaryTree(char c) {
        root = new BinaryNode(c);
    }

    public void addToTree(String s) {
        BinaryNode node = this.root;
        int length = s.length();
        for (int i = s.length()-1; i >= 0; i--) {
            BinaryNode newNode;
            if (s.charAt(i) == '0') {
                 newNode = addCharToTree(node.left, s.charAt(i));
                 node.left = newNode;
            } else {
                newNode = addCharToTree(node.right, s.charAt(i));
                node.right = newNode;
            }
            node = newNode;
        }
    }

    private BinaryNode addCharToTree(BinaryNode node, char c) {
        if (node == null)
            return new BinaryNode(c);
        return node;
    }


}


public class Solution {

  private static void findMagicalPairs(List<Integer> list) {
        // for creating 32 char long binary string list
        List<String> binaryNumberList = list.stream()
                .map(num -> Long.toBinaryString( Integer.toUnsignedLong(num) | 0x100000000L ).substring(1))
                .collect(Collectors.toList());
        // dummy character as root
        BinaryTree binaryTree = new BinaryTree('c');
        binaryNumberList.forEach(binaryTree::addToTree);
        List<Boolean> booleanList = binaryNumberList.stream()
                                     .map(s -> hasMagicalPair(s, binaryTree.root))
                                     .collect(Collectors.toList());
    }

    private static boolean hasMagicalPair(String s, BinaryNode node) {
        if (s == null || s.length() == 0)
            return true;
        if (node == null)
            return false;
        String substring = s.substring(0, s.length() - 1);
        if (s.charAt(s.length()-1) == '1')
            return hasMagicalPair(substring, node.left) ;
        return hasMagicalPair(substring, node.left) || hasMagicalPair(substring, node.right);
    }

}

推荐阅读