java - 如何检查数组中整数值之间的整除性

Question

假设，我有一个整数数组或列表(没有重复)，例如:

int[] = { 35 165 21 5 6 55 7 42}

现在我需要根据两个规则过滤列表:

1. 检查一个数字是否可以被数组中的所有其他数字整除。
2. 如果数字大于其除数，则保留最大的那个。

让我进一步解释一下我的问题:

假设我在前面的数组中选择 165。现在，165 不能被 35、6、7、42 整除；但它可以被 5 和 55 整除。因此，我从数组中删除 5 和 55。同样，21、6、7也被删除。因此，我的最终列表是:165, 35, 42。

我尝试用下面的代码解决这个问题:

Set<Integer> MFV = new HashSet<>();
for(i = 0; i < lwd.length; i++)
{
    for(j = i; j < lwd.length; j++)
    { 
        if(i != j && (lwd[i] % lwd[j] == 0 || lwd[j] % lwd[i] == 0))
        {
            if(lwd[i] > lwd[j])
                MFV.add(lwd[i]);
            //else
                //MFV.add((int)lwd[j]);
        } 
    }
}

System.out.println();
for(Iterator<Integer> it = MFV.iterator(); it.hasNext();)
{
    System.out.print(it.next() + " ");
}

但这给出的结果是 35,​​ 165, 21。

Answer 1

你的实现不起作用，有两个原因:

1. 您过早地将元素添加到不可整除集合中:仅因为第 i 个元素除以第 j 个元素并不意味着不应删除第 i 个元素。它仅意味着应删除第 j 个元素。随着循环继续，很可能也必须删除第 i 个元素，但为时已晚，因为它已经添加到不可整除的集合中。

2. 在不可分集合中添加元素的条件lwd[i] > lwd[j]是不够的:例如x > c * x 永远不会为真，从而阻止将 c * x 添加到集合中。

根据数字的顺序，纯粹出于运气，实现可能会给出正确的结果。通过重新排列数字很容易打破它，例如，这个顺序演示了我上面指出的两个问题:

int[] lwd = {35, 21, 5, 6, 55, 7, 42, 165};

按照这个顺序，程序输出:35, 21。

也就是说，21 被错误地添加到集合中，在考虑21 vs 42之前，这将消除21。这说明了第一个问题。

缺失的 165 说明了第二个问题:在 lwd[i] > lwd[j] 比较中，165 永远是第二个操作数，因为它位于列表的末尾，它比所有其他元素都大，所以它永远不会被添加到不可分集合中。

这是解决这些问题的替代版本:

    int[] nums = {35, 21, 5, 6, 55, 7, 42, 165};
    boolean[] removed = new boolean[nums.length];

    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j] && nums[i] % nums[j] == 0) {
                removed[j] = true;
            } else if (nums[i] < nums[j] && nums[j] % nums[i] == 0) {
                removed[i] = true;
            }
        }
    }

    for (int i = 0; i < nums.length; ++i) {
        if (!removed[i]) {
            System.out.print(nums[i] + " ");
        }
    }

    System.out.println();