2

考虑 9 个变量,每个变量的值可以从 1 到 9。什么是检查每个变量是否具有不同值的好且快速的方法。我想到的第一个想法是总结它们,看看它是否等于,n(n+1)/2但这绝非万无一失。有任何想法吗?

编辑:非常感谢大家。完全忘记了赛特。我真是个菜鸟。

4

4 回答 4

6

将它们全部添加到一个 Set 中,并检查 Set 的大小是否为 9。

例如,要检查 9 个数组int是否都不同:

int[] array = new int[9];
// fill array
Set<Integer> set = new HashSet<Integer>();
for (int i : array)
    set.add(i);
boolean allDistinct = set.size() == 9;

集合完成所有工作,因为集合只允许添加不同的值。如果任何值相同,则大小将小于 9。

这种技术适用于任何类型的值类型、任何范围和任何数量的值。

于 2013-04-05T14:30:08.133 回答
6

从设置位 0 到 9 的位掩码开始,然后清除与每个变量的值对应的位。如果生成的位掩码是 2 的幂,则所有值都是不同的+;否则,有重复。

int a, b, c, d, e, f, g, h, i;
int mask = 0x3FF; // bits zero through 9 are set
mask &= ~(1<<a);
mask &= ~(1<<b);
...
mask &= ~(1<<i);
if ((mask & -mask) == mask) {
    // all bits were distinct
}

有关最后一个条件中使用的位技巧的解释,请参见此答案


+你有十个可能的值和九个变量;为了使这九个值不同,它们必须从最初设置所有十位的位掩码中清除十位中的九位。删除十分之九的位只剩下一位设置为1,这意味着结果是 2 的幂。

于 2013-04-05T14:30:44.077 回答
4

使用 XOR 查找重复数字是一个技巧。

int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 5, 9 };
int answer = 0;
for (int i = 0; i < arr.length; i++) {
    answer = answer ^ (arr[i] + 1) ^ i;
}
System.out.println(answer - 1);

输出:

5
于 2013-04-05T14:32:05.283 回答
0

此算法适用于任何数字计数,但每个数字必须在区间 <0, 31> 内,或者您可以将区间 <0, 63> 的掩码类型更改为 long。

int[] numbers = {0, 1, 2, 3, 3, 5, 6, 7};

int mask = 0;
for (int number : numbers) {
    int bit = 1 << number;

    if ((mask & bit) > 0) {
        System.out.println("Found duplicity " + number);
        return;
    }

    mask |= bit;
}

System.out.println("No duplicity");
于 2019-03-04T22:18:52.370 回答