1

免责声明：这是作业，所以请不要只给我代码，我想解释一下我如何用尽可能少的实际代码来做这件事。

所以我有两个未排序且长度相等的整数数组，并且可以包含重复值。由于这是家庭作业，有一个奇怪的情况是我不允许使用 java.utils 中的任何内容或对数组进行排序。

我应该检查两个数组是否包含相同的元素，而不管顺序如何。因此比较数组 [5, 6, 7, 5, 6, 3] 和 [6, 6, 7, 5, 5, 3] 将返回 true，同时比较 [7,7 8] 和 [7, 8, 8 ] 不会。

我不知道如何做到这一点，我已经搜索了问题，但它们似乎都使用了 java.utils 中的某些东西，或者数组不包含重复项。我尝试循环遍历第一个数组中的每个值，并为每个值循环遍历第二个数组，检查该值是否存在于那里，但它会因重复而出错。

我会很感激任何形式的帮助、建议或正确方向的提示。谢谢！

4

8 回答 8

5

如何依次从第一个 int 数组中取出每个元素，并检查是否在第二个 int 数组中找到它。为了使这个想法奏效，您需要创建一个布尔值数组，这些值都初始化为false，以指示是否使用了第二个 int 数组中的值。然后，当您从第一个数组中找到每个值时，将布尔数组中的相应元素设置为true.

于 2013-10-05T22:04:22.157 回答
3

一种方法是遍历第一个数组并删除与第二个数组中相同的元素。

当您无法从第二个数组中的第一个数组中找到一个元素时，则数组不相等。当您从第二个数组中的第一个数组中找到最后一个元素时，这些数组是相等的。

如果不修改数组，那么您必须先克隆您更改的数组。

于 2013-10-05T22:14:16.117 回答
1

这是一个解决方案，在较长的数组上可能会变慢，因为它是 O(n²)

// return how often n appears in an array
public static int count(int n, int[] array) { ... }

public static boolean equalarrays(int[] arr1, int[] arr2) {
   for (int i: arr1) {
       if (count(i, arr1) != count(i, arr2)) return false;
   }
   return arr1.length == arr2.length;
}
于 2013-10-05T23:04:49.130 回答
1 
1   public static boolean compare(int[] a, int[] b)
2   {
3       if(a.length != b.length) return false;
4
5       aloop:for(int i = 0; i < a.length; ++i)
6       {
7           bloop:for(int j = 0; j < b.length; ++j)
8           {
9               if(a[i] == b[j])
10              {
11                  for(int k = j; k < i; ++k)
12                  {
13                      if(a[k] == b[j])    continue bloop;
14                  }
15
16                  continue aloop;
17              }
18          }
19
20          return false;
21      }
22
23      return true;
24  }

这基本上是说：取两个相同大小的数组(3) a和b，迭代槽a (5)，迭代槽b (7)，比较(9)a的每个元素的元素，如果任何元素等于 的元素：b ba

  • 如果为真：检查该元素是否a已经被处理，迭代 a-loop (11)的索引并与已经处理的元素(13)进行比较。
    • 如果为真：获取下一个元素b并重复。(13)
    • 如果为假：获取下一个元素a并重复。(17)
  • 如果为假：好吧，当没有b等于元素的元素时a返回假（18）

如果我们到第(23)行，所有 的元素b都是 的元素a。返回真。

编辑：此外，您可以反转 aloop 和 bloop 以获得一些额外的性能。（我没有把它放到主代码块中，因为它容易混淆人们。）

bloop:for(int j = 0; j < b.length; ++j)
// could be written as
bloop:for(int j = b.length; (--j) >= 0; )
// which is faster as the comparison and incrementation step are merged into one
于 2013-10-06T00:03:46.347 回答
0

一种常见的通用方法是对两个数组进行排序，然后比较它们。对于任何两个数组，这种方法总是会在可预测的时间内成功。我认为没有任何算法的最坏情况时间会明显优于对数组进行排序所需的时间。

然而，在许多情况下，拥有一种“通常”比排序数组更快的方法可能会很有用。作为一个简单的例子，假设对于每个整数X计算 (X*(X+123456))，并将这些值的总和相加（作为 a long）如果两个列表包含相同的值，以任何顺序，它们的总和应该相等. 列表可能包含不同的值，但仍然产生相同的总和，但在大多数情况下，列表包含不同的值，它们的总和可以被识别为不同，而不必经历对列表进行排序的麻烦。

您可能要考虑的另一件事是“哈希基数排序”。基数排序的工作原理是让每遍将事物分成桶，然后输出第一个桶的内容，然后输出第二个、第三个、第四个、第五个桶的内容。打孔卡过去以这种方式分类，使用一台机器检查每张卡上的一列，然后根据打孔的内容将每张卡放入 13 个桶中的一个。可以使用 2^32 桶的一次遍历、65,536 桶的两次遍历、256 桶的四次遍历等对任意数量的 32 位整数进行排序。不过，基数排序的一个小麻烦是，事物的分布各种桶通常会严重倾斜。如果一个人定义了一个将输入值映射到例如的函数 从 0 到 255 的数字，这样 1/256 的输入将分配给每个值，然后可以在线性时间内将“排序”列表的任务减少为对 256 个列表进行排序的任务，每个列表的大小为 1/256 . 请注意，生成的序列不会在传统意义上“排序”，但是包含相同项目的两个列表将以相同的方式“排序”。

于 2013-10-13T18:07:59.107 回答
0

一个简单的解决方案是复制两个数组，然后对副本进行排序和比较。这是O(NlogN)如果你使用一个好的排序算法。如果你使用正确的库方法，你可以用大约 3 行代码编写它。

@Andy256 和 @Stochastically 的解决方案都应该有效，但它们都是O(N^2).

于 2013-10-05T23:59:55.943 回答
0

这是一个有趣的活动，我会在自己的时间做。我建议让两个 ArrayList 包含两个数组表的所有值。我这样做是因为您可以使用该remove()方法。循环遍历给定的第一个数组的所有元素。那将是您的参考数组。在参考数组的第一次迭代中获取对象。然后检查您的其他数组是否包含它。如果没有，则检查失败，您可以false当场返回，如果确实如此：删除它，然后获取参考数组的下一次迭代。

即使您不想要代码，它也位于 pastebin 中：http: //www.pastebin.com/3BEV2CqH 它接受一个Object[] ... tables参数并使用equals方法进行比较。如果你能像我一样完成它，我相信你的老师会感到惊讶。

于 2013-10-05T23:09:13.867 回答
0

这是一个解决方案。反正帖子老了

public static boolean equality(int[] list,int[] list2)
  {
    boolean result = false;
    int correct = 0;
    if(list.length == list2.length)
    {
      for(int i = 0; i< list.length; i++)
      {
        for(int j = 0; j < list2.length; j++)
        {
          if(list[i] == list2[j])
          {
            correct++;
            if(correct == list.length && correct == list2.length)
            {
              result = true;
            }
          }
        }
      }
    }
    return result;
  }
}
于 2016-01-09T15:53:58.147 回答