如何找到在矩阵中只出现一次的数字？

Question

我有一个名为 m 的给定矩阵，它的维度是 n x n，它包含整数。我需要将只出现一次的数字复制到一个名为 a.

的新数组中

我认为逻辑是为矩阵中的每个数字创建一个 for 循环并将其与其他所有数字进行比较，但我不知道如何使用代码实际执行此操作。

我只能使用循环（没有地图等），这就是我想出的：

public static void Page111Ex14(int[][] m) {

    int previous = 0, h = 0;
    
    int[] a = new int[m.length*m[0].length];
    
    for (int i = 0; i < m.length; i++) {
        for (int j = 0; j < m[0].length; j++) {
            previous = m[i][j];
            
            if (m[i][j] != previous) {
                a[h] = m[i][j];
                h++;
            }
        }
    }

虽然可能不正确。

Answer 1

看起来不太好：

previous = m[i][j];

if (m[i][j] != previous) {
    a[h] = m[i][j];
    h++;
}

您将 m[i][j] 分配给了 previous 然后您检查是否 if (m[i][j] != previous)?

这个任务对数字的取值范围有限制吗？

Answer 2

再循环一遍，看有没有重复的。假设您可以使用标签，答案可能看起来有点像这样：

public static int[] getSingleInstanceArrayFromMatrix(int[][] m) {
        int[] a = new int[m.length * m[0].length];

        // Main loop.
        for (int x = 0; x < m.length; x++) {
            for (int y = 0; y < m[0].length; y++) {

                // Gets the current number in the matrix.
                int currentNumber = m[x][y];

                // Boolean to check if the variable appears more than once.
                boolean isSingle = true;

                // Looping again through the array.
                checkLoop:
                for (int i = 0; i < m.length; i++) {
                    for (int j = 0; j < m[0].length; j++) {
                        
                        // Assuring we are not talking about the same number in the same matrix position.
                        if (i != x || j != y) {
                            // If it is equal to our current number, we can update the variable and break.
                            if (m[i][j] == currentNumber) {
                                isSingle = false;
                                break checkLoop;
                            }
                        }
                    }
                }

                if (isSingle) {
                    a[(x * m.length) + y] = currentNumber;
                }
            }
        }

        return a;
    }

不确定它是否最有效，但我认为它会起作用。没有列表等的帮助，很难形成最终数组。由于未分配的值将默认为 0，如果您查找返回的数组，任何 actual 零（即它“应该”基于矩阵）将不会被检测到。但是，如果有这样的限制，我想它并不是至关重要的。

Answer 3

这是您可以直接使用 HashMap 解决的问题之一，它会为您完成工作。您遍历二维数组，使用 HashMap 存储每个元素及其出现次数，然后遍历 HashMap 并将出现次数为 1 的所有元素添加到列表中。然后将此列表转换为数组，这是您需要 return.

复杂度为 O(n*n)，其中 n 是方阵 m 的一维。

import java.util.*;
import java.io.*;
    
class GetSingleOccurence
{
    static int[] singleOccurence(int[][] m)
    {
        // work with a list so that we can append to it
        List<Integer> aList = new ArrayList<Integer>();

        HashMap<Integer, Integer> hm = new HashMap<>();

        for (int row = 0; row < m.length; row++) {
            for (int col = 0; col < m[row].length; col++) {
                if (hm.containsKey(m[row][col]))
                    hm.put(m[row][col], 1 + hm.get(m[row][col]));
                else
                    hm.put(m[row][col], 1);
            }
        }

        for (Map.Entry entry : hm.entrySet())
        {
            if (Integer.parseInt(String.valueOf(entry.getValue())) == 1)
                a.add(Integer.parseInt(String.valueOf(entry.getKey())));
        }

        // return a as an array
        return a.toArray(new int[a.size()]);
    }
    
    public static void main(String args[])
    {
            // A 2D may of integers with some duplicates

            int[][] m = { { 1, 2, 3, 4, 5 },
                            { 6, 7, 8, 9, 10 },
                            { 11, 12, 12, 14, 15 },
                            { 16, 17, 18, 18, 20 },
                            { 21, 22, 23, 24, 25 } };
    
            a = singleOccurence(m);
    }
}

Answer 4

最好使用布尔数组 boolean[] dups 来跟踪重复的数字，因此在第一次传递期间填充此中间数组并计算单打的数量。

然后创建适当大小的结果数组，如果此数组不为空，则在 dups 的第二次迭代中将标记为单值的值复制到结果数组。

public static int[] getSingles(int[][] arr) {
    int n = arr.length;
    int m = arr[0].length;
    boolean[] dups = new boolean[n * m];
    int singles = 0;
    for (int i = 0; i < dups.length; i++) {
        if (dups[i]) continue; // skip the value known to be a duplicate
        int curr = arr[i / m][i % m];
        boolean dup = false;
        for (int j = i + 1; j < dups.length; j++) {
            if (curr == arr[j / m][j % m]) {
                dup = true;
                dups[j] = true;
            }
        }
        if (dup) {
            dups[i] = true;
        } else {
            singles++;
        }
    }
    // debugging log
    System.out.println("singles = " + singles + "; " + Arrays.toString(dups));
    int[] res = new int[singles];
    if (singles > 0) {
        for (int i = 0, j = 0; i < dups.length; i++) {
            if (!dups[i]) {
                res[j++] = arr[i / m][i % m];
            }
        }
    }
    return res;
}

测试：

int[][] mat = {
    {2, 2, 3, 3},
    {4, 2, 0, 3},
    {5, 4, 2, 1}
};    
System.out.println(Arrays.toString(getSingles(mat)));

输出（包括调试日志）：

singles = 3; [true, true, true, true, true, true, false, true, false, true, true, false]
[0, 5, 1]

Answer 5

您对 previous 的使用只是一个即将出现的想法。删除它，并填充一维a。使用两个嵌套的 for 循环查找重复项需要 n⁴ 个步骤。但是，如果您对数组 a 进行排序 - 对值进行排序 - 成本 n² log n²，您可以更快地找到重复项。

Arrays.sort(a);
int previous = a[0];
for (int h = 1; h < a.length; ++h) {
    if (a[h] == previous)...
    previous = a[h];
 ...

看起来这个解决方案几乎已经在 class 中处理过了。

如何找到在矩阵中只出现一次的数字？

How to find numbers that appear only once in a matrix?

java

arrays

for-loop

matrix