检查行和列中的副本2D数组

时间:2022-09-26 21:31:48

how would I go about checking a duplicate for columns and rows and return true or false depending if there's duplicates. For example

如何检查列和行的副本,并根据是否有副本返回true或false。例如

1 2 3

1 2 3

3 1 2

3 1 2

2 3 1

1 2 3

Would return true because no duplicates, but..

因为没有重复,所以会返回true。

1 2 2

1 2 2

3 2 3

3 2 3

2 1 1

2 1 1

would return false because there is a duplicate in column 2 {2, 2, 1}.

将返回false,因为在第2列{2,2,1}中有一个副本。

How would I go about checking for if there are in duplicates in the rows and then checking if there are duplicates in the columns?

如果在行中有重复项,然后检查列中是否有重复项,我将如何进行检查?

So far I have only the following:

到目前为止,我只有以下几点:

public static boolean hasDuplicates(int [][] inArray)
{
   for (int row = 0; row < inArray.length; row++)
   {
      int rowCheck = inArray[row][inArray.length];
      for (int col = 0; col < inArray[row].length; col++)
      {

      }
   }
   return false;
}

So I need to take in an array and check if there are any duplicates among the columns or rows. Any pointers? Thank you!

所以我需要取一个数组,检查列和行之间是否有重复。指针吗?谢谢你!

NOTE: This cannot be done with outside methods

注意:这不能用外部方法完成

4 个解决方案

#1


1  

Go through each value in the row. For every value, check and see if any of the values after that value are the same. If the value is the same, return true (you've found a duplicate). If none of the values are the same, increment your index and do the same for the next row. Every row will take at most n(n+1)/2 comparisions which isn't wonderful. So if n is the number of columns and m in the number of rows, this will run, worst case m(n(n+1)/2) times.

遍历行中的每个值。对于每个值,检查并查看该值之后的任何值是否相同。如果值相同,返回true(您已经找到了一个副本)。如果所有的值都不相同,那么增加索引并对下一行执行相同的操作。每一行最多有n(n+1)/2个比较,这并不好。如果n是列数,m是行数,最坏情况是m(n(n+1)/2)次。

Here is an example of how it would work for the rows:

下面是它如何为行工作的一个例子:

/**
 * Return flag indicating if there are duplicates in the rows of the 2D array
 * 
 * @return true if a row has duplicates, else false
 */
public boolean hasDuplicatesInRows(int[][] inArray)
{
    for (int row = 0; row < inArray.length; row++)
    {
        for (int col = 0; col < inArray[row].length; col++)
        {
            int num = inArray[row][col];
            for (int otherCol = col + 1; otherCol < inArray.length; otherCol++)
            {
                if (num == inArray[row][otherCol])
                {
                    return true;
                }
            }
        }
    }

    return false;
}

That would be pretty easy to extend to do columns as well. I will leave that for you to do though.

这也很容易扩展到列。我把这个留给你们来做。

If you used an efficient sorting method and sorted all the rows, you could just go down the line and see if any value was equal to the value after it. If it is, return true, else return false. This would be more efficient if you had a large data set.

如果您使用高效的排序方法并对所有行进行排序,那么您可以沿着这条直线向下看,看看是否有任何值等于它之后的值。如果是,返回true,否则返回false。如果你有一个大的数据集,这会更有效率。

#2


1  

Let's say you create a method that operates on a single-dimensional array. You break the problem down into extracting strips of numbers from your 2d array into a 1d array. It's signature might look like boolean containsDupes(int[] strip) { ... }.

假设您创建了一个对一维数组进行操作的方法。您将问题分解为从2d数组中提取条状数字到一维数组中。它的签名可能看起来像boolean containsDupes(int[] strip){…}。

There are a couple of approaches in that method that would make it easier to solve. One would be to sort that array so the dupes are next to each other. Another would be to populate a HashSet with each value and compare the size of the Set with the length of your array.

该方法中有两种方法可以使其更容易求解。一种方法是对数组进行排序,这样被模仿的对象就会挨着。另一种方法是用每个值填充HashSet,并将集合的大小与数组的长度进行比较。

#3


1  

A more compact way of achieving this task is to add all the values to a Set and then compare the number of unique elements in the Set to the original row size using guava.

实现此任务的一种更紧凑的方法是将所有的值添加到一个集合中,然后使用guava将集合中唯一元素的数量与原来的行大小进行比较。

public static boolean hasDuplicates(int [][] inArray) {
    for (int row = 0; row < inArray.length; row++) {
        int curRow = inArray[row];
        Set set = Sets.newHashSet(Arrays.asList(curRow));
        if (set.size() < curRow.length) {
            return true;
        }
    }
    return false;
}

#4


1  

for rows, try following this sort of procedure:

对于行,请尝试按照以下步骤:

boolean dup = false;
for (int k = 0; k < inArray[0].length){ //loop through columns
  for (i = 0; i < inArray.length-1; i++) {
    for (int j = i; j < inArray.length; j++){
      if (inArray[k][i] == inArray[k][j]){
        dup = true;
        break;
      }
    }
  }
}

so, you're starting at the first element, then scanning from element 2 to n (ie number of columns). If a match is found, then you're setting the boolean to true. If no match, then i is incremented and the inner for loop is scanning from element 3 to n.

从第一个元素开始,然后从元素2扫描到n(即列数)。如果找到匹配,则将布尔值设置为true。如果没有匹配,那么i将增加,内部for循环将从元素3扫描到n。

Follow a similar procedure for the columns, and you're done!

对列执行类似的过程,您就完成了!

#1


1  

Go through each value in the row. For every value, check and see if any of the values after that value are the same. If the value is the same, return true (you've found a duplicate). If none of the values are the same, increment your index and do the same for the next row. Every row will take at most n(n+1)/2 comparisions which isn't wonderful. So if n is the number of columns and m in the number of rows, this will run, worst case m(n(n+1)/2) times.

遍历行中的每个值。对于每个值,检查并查看该值之后的任何值是否相同。如果值相同,返回true(您已经找到了一个副本)。如果所有的值都不相同,那么增加索引并对下一行执行相同的操作。每一行最多有n(n+1)/2个比较,这并不好。如果n是列数,m是行数,最坏情况是m(n(n+1)/2)次。

Here is an example of how it would work for the rows:

下面是它如何为行工作的一个例子:

/**
 * Return flag indicating if there are duplicates in the rows of the 2D array
 * 
 * @return true if a row has duplicates, else false
 */
public boolean hasDuplicatesInRows(int[][] inArray)
{
    for (int row = 0; row < inArray.length; row++)
    {
        for (int col = 0; col < inArray[row].length; col++)
        {
            int num = inArray[row][col];
            for (int otherCol = col + 1; otherCol < inArray.length; otherCol++)
            {
                if (num == inArray[row][otherCol])
                {
                    return true;
                }
            }
        }
    }

    return false;
}

That would be pretty easy to extend to do columns as well. I will leave that for you to do though.

这也很容易扩展到列。我把这个留给你们来做。

If you used an efficient sorting method and sorted all the rows, you could just go down the line and see if any value was equal to the value after it. If it is, return true, else return false. This would be more efficient if you had a large data set.

如果您使用高效的排序方法并对所有行进行排序,那么您可以沿着这条直线向下看,看看是否有任何值等于它之后的值。如果是,返回true,否则返回false。如果你有一个大的数据集,这会更有效率。

#2


1  

Let's say you create a method that operates on a single-dimensional array. You break the problem down into extracting strips of numbers from your 2d array into a 1d array. It's signature might look like boolean containsDupes(int[] strip) { ... }.

假设您创建了一个对一维数组进行操作的方法。您将问题分解为从2d数组中提取条状数字到一维数组中。它的签名可能看起来像boolean containsDupes(int[] strip){…}。

There are a couple of approaches in that method that would make it easier to solve. One would be to sort that array so the dupes are next to each other. Another would be to populate a HashSet with each value and compare the size of the Set with the length of your array.

该方法中有两种方法可以使其更容易求解。一种方法是对数组进行排序,这样被模仿的对象就会挨着。另一种方法是用每个值填充HashSet,并将集合的大小与数组的长度进行比较。

#3


1  

A more compact way of achieving this task is to add all the values to a Set and then compare the number of unique elements in the Set to the original row size using guava.

实现此任务的一种更紧凑的方法是将所有的值添加到一个集合中,然后使用guava将集合中唯一元素的数量与原来的行大小进行比较。

public static boolean hasDuplicates(int [][] inArray) {
    for (int row = 0; row < inArray.length; row++) {
        int curRow = inArray[row];
        Set set = Sets.newHashSet(Arrays.asList(curRow));
        if (set.size() < curRow.length) {
            return true;
        }
    }
    return false;
}

#4


1  

for rows, try following this sort of procedure:

对于行,请尝试按照以下步骤:

boolean dup = false;
for (int k = 0; k < inArray[0].length){ //loop through columns
  for (i = 0; i < inArray.length-1; i++) {
    for (int j = i; j < inArray.length; j++){
      if (inArray[k][i] == inArray[k][j]){
        dup = true;
        break;
      }
    }
  }
}

so, you're starting at the first element, then scanning from element 2 to n (ie number of columns). If a match is found, then you're setting the boolean to true. If no match, then i is incremented and the inner for loop is scanning from element 3 to n.

从第一个元素开始,然后从元素2扫描到n(即列数)。如果找到匹配,则将布尔值设置为true。如果没有匹配,那么i将增加,内部for循环将从元素3扫描到n。

Follow a similar procedure for the columns, and you're done!

对列执行类似的过程,您就完成了!