查找产品的算法[关闭]

Question

我在编码挑战中遇到了这个问题而无法解决它。这是问题陈述：

给定一系列交易成本t，返回一系列预期成本e，如果除了e [i]之外的t中所有交易成本的乘积是偶数，则返回0，否则它是1（即对于t [i]中的任何元素） ，找到除t [i]之外的所有t元素的乘积。如果该乘积是偶数，则t [i]的结果为0，否则为1）。

例如t = [1,2,3,4]，e = [0,0,0,0]

说明：对于t，所有产品均为：[24,12,8,6]

约束：在O（n）中进行，没有除法。

仅供参考，我是用O（N ^ 2）做的，但在O（N）中无法解决

我的解决方案

int[] arr = {1, 2, 3, 4};
    int[] res = new int[arr.length];
    for(int i = 0; i < arr.length; i++){
        int prd = 1;
        for(int j = 0; j < arr.length; j++){
            if(i == j) {
                continue;
            }
            prd *= arr[j];
        }

        if((prd & 1) == 0){
            res[i] = 0;
        }else {
            res[i] = 1;
        }
    }

Answer 1

你不需要分裂;你需要的只是一个简单的奇数/偶数检查。无论你如何做到这一点都很好;例如，除了最后一点之外，屏蔽掉一切。

很简单，如果所有元素都是奇数，则e是1的向量。如果一个元素是偶数，则e是所有0的向量，除了那个位置，即1。如果多个元素是偶数，则e是0的向量。

这需要单次通过t（即O（N））来找到偶数元素的数量;然后你可以在O（N）时间内生成e