Return 在所有矩阵行中具有重复元素的数组

Question

目前正在研究一种方法，该方法将 n*n 矩阵作为输入，returns 是一个由每个子数组中找到的所有元素组成的数组。但是，因为我需要它也包括重复项等，所以它比我想象的要难。

然而，用谷歌搜索它，仍然没有找到符合我的重复标准的解决方案。

目前我有这个，它将第一行的元素与其他每一行及其所有元素进行比较。如果计数器达到它确认该元素确实存在于所有行中的长度，它会将它添加到数组中。但是，这有缺点。首先，由于我在开始时创建了一个具有最大可能长度的集合数组，它可能 return 一个包含不需要的 0 的数组。其次，重复的部分没有正常工作，很难在那里实施检查。

我需要的input/output例子：

Input matrix: {{2,2,1,4},{4,1,2,2},{7,1,2,2},{2,10,2,1}}
Desired output: {1, 2, 2}
My output: {2, 2, 1, 0}

Input matrix:  {{2,2,1,4},{4,1,3,2},{7,1,9,2},{2,10,2,1}}
Desired output: {1, 2}
My output: {2, 2, 1, 0}

public static int[] common_elements(int[][] matrix){
        int[] final_array = new int[matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            int counter = 0;
            for (int j = 1; j < matrix.length; j++) {
                for (int k = 0; k < matrix.length; k++) {
                    if(matrix.[0][i] == matrix.[j][k]){
                        counter += 1;
                        break;
                    }
                }
            }
            if(counter == a.length-1){
                final_array[i] = a[0][i];
            }
        }

        return final_array;
    }

编辑：这是我最终组合在一起的，符合我的要求并且工作完美，有评论

public static int[] repetitiveInts(int[][] a){
        //This is a method declared outside for sorting every row of the matrix ascending-ly before I do the element search.
        for (int i = 0; i < a.length; i++) { 
            sorting(a[i]);
        }
        //Declaring a LinkedList in order to add elements on the go
        LinkedList<Integer> final_list= new LinkedList<Integer>();
        //Iterating through the matrix with every element of the first row, counting if it appears in every row besides the first one.
        for (int i = 0; i < a.length; i++) {
            int counter = 0;
            for (int j = 1; j < a.length; j++) {
                for (int k = 0; k < a.length; k++) {
                 //Checking if an element from the other rows match
                    if(a[0][i] == a[j][k]){
                        a[j][k] = a[0][i]-1; //If a match is found, the element is changed so finding duplicates is possible.
                        counter += 1;
                        break; //Breaking and checking the next row after one row checks out successfully.
                    }
                }
            }
            //If the element is indeed in every row, adds it to the lit.
            if(counter == a.length-1){
                final_list.add(a[0][i]);
            }
        }
        //Since I had to return a regular int[] array, converting the LinkedList into an array.
        int[] final_realarray= new int[final_list.size()];
        for (int i = 0; i < final_list.size(); i++) {
            final_realarray[i] = final_list.get(i);
        }
        return final_realarray;

感谢帮助:)

Answer 1

解决此问题的最有效方法是为 中的每个 嵌套数组 创建一个 频率直方图 ]矩阵（即确定嵌套数组中每个元素的出现次数）。

每个 直方图 将由 Map<Integer, Integer> 表示（数组元素作为 key，它的出现作为值）。要生成直方图，只需要通过阵列一次。在下面的解决方案中，此逻辑位于 getFrequencies() 方法中。

创建所有 直方图后 我们必须合并它们。根据集合论，我们正在寻找 keys 的 intersection in all 直方图。 IE。我们只需要在每个 直方图 中出现在 至少一次 的那些 keys 和每个 [=对于那个 key，50=]key 将是所有 histograms 中最小的。这个逻辑放在getCommonElements().

为了创建合并直方图，我们可以选择任何直方图（在下面的代码中使用第一个直方图frequencies.get(0).keySet()) 并遍历其键。然后在嵌套循环中，对于每个键，我们需要在每个直方图[=]中找到与之关联的最小值 107=] 在列表中（提醒：这将是键 出现的最少次数）。

同时，在合并直方图的同时，我们还可以通过将所有最小频率相加来找到 结果数组 的长度 .这个小的优化将允许避免对合并的地图进行第二次迭代。

所需的最后一步是使用 合并直方图 中的键填充结果数组 commonElements。每个键的 Value 表示它必须在结果数组中放置多少次。

public static void main(String[] args) { System.out.println(Arrays.toString(commonElements(new int[][]{{2,2,1,4},{4,1,2,2},{7,1,2,2},{2,10,2,1}}))); System.out.println(Arrays.toString(commonElements(new int[][]{{2,2,1,4},{4,1,3,2},{7,1,9,2},{2,10,2,1}}))); }

public static int[] commonElements(int[][] matrix){ List<Map<Integer, Integer>> frequencies = getFrequencies(matrix); return getCommonElements(frequencies); } private static List<Map<Integer, Integer>> getFrequencies(int[][] matrix) { List<Map<Integer, Integer>> frequencies = new ArrayList<>(); for (int[] arr: matrix) { Map<Integer, Integer> hist = new HashMap<>(); // a histogram of frequencies for a particular array for (int next: arr) { // hist.merge(next, 1, Integer::sum); Java 8 alternative to if-else below if (hist.containsKey(next)) { hist.put(next, hist.get(next) + 1); } else { hist.put(next, 1); } } frequencies.add(hist); } return frequencies; }

private static int[] getCommonElements(List<Map<Integer, Integer>> frequencies) { if (frequencies.isEmpty()) { // return an empty array in case if no common elements were found return new int[0]; } Map<Integer, Integer> intersection = new HashMap<>(); int length = 0; for (Integer key: frequencies.get(0).keySet()) { // int minCount = frequencies.get(0).get(key); // min number of occurrences of the key in all maps for (Map<Integer, Integer> map: frequencies) { int nextCount = map.getOrDefault(key, 0); minCount = Math.min(nextCount, minCount); // getOrDefault is used because key might not be present if (nextCount == 0) { // this key isn't present in one of the maps, no need to check others break; } } if (minCount > 0) { intersection.put(key, minCount); length += minCount; } } int[] commonElements = new int[length]; int ind = 0; for (int key: intersection.keySet()) { int occurrences = intersection.get(key); for (int i = 0; i < occurrences; i++) { commonElements[ind] = key; ind++; } } return commonElements; }

输出

[1, 2, 2] [1, 2]

旁注： 不要违反 naming conventions，使用 camel-case 作为方法和变量名称。

更新

我已经根据需要实现了基于 arrays 和 lists 的 brute-force 解决方案。

最重要的是，对于此任务，您需要两个列表：一个用于存储元素，另一个用于存储[=91] =]频率。列表通过索引绑定在一起。而这两个list基本上就是在模仿一个map，坦白说是一个非常低效的（但这是一个要求）。另一种可能性是用两个 int 字段实现一个 class 来表示一个公共元素的数据，然后存储这个 class 在单个列表中。但在这种情况下，检查特定元素是否已经存在于 list 中的过程将更加冗长。

整体逻辑和上面的方案有一些相似之处。

首先，我们需要在矩阵（matrix[0]）中选择一个数组并比较它的所有唯一元素 与所有其他数组的内容相对。每个 element with non-zero frequency 将反映在 elements 列表和frequencies 的列表在两者的相同索引处。在创建结果数组时，代码依赖于这些列表中的相应索引。

public static int[] commonElements(int[][] matrix){ if (matrix.length == 0) { // case when matrix is empty - this condition is required because farther steps will lead to IndexOutOfBoundsException return new int[0]; } if (matrix.length == 1) { // a small optimization return matrix[0]; } // Map<Integer, Integer> frequencyByElement = new HashMap<>(); // to lists will be used instead of Map, because of specific requirement for this task List<Integer> frequencies = new ArrayList<>(); // lists will be bind together by index List<Integer> elements = new ArrayList<>(); int length = 0; // length of the resulting array for (int i = 0; i < matrix[0].length; i++) { if (elements.contains(matrix[0][i])) { // that means this element is a duplicate, no need to double-count it continue; } int currentElement = matrix[0][i]; int minElementCount = matrix[0].length; // min number of occurrences - initialized to the max possible number of occurrences for the current array // iterating over the all nested arrays in matrix for (int row = 0; row < matrix.length; row++) { int localCount = 0; // frequency for (int col = 0; col < matrix[row].length; col++) { if(matrix[row][col] == currentElement){ localCount++; } } if (localCount == 0) { // element is absent in this array and therefore has to be discarded minElementCount = 0; break; // no need to iterate any farther, breaking the nested loop } minElementCount = Math.min(localCount, minElementCount); // adjusting the value the min count } // frequencyByElement.put(currentElement, minElementCount); // now we are sure that element is present in all nested arrays frequencies.add(minElementCount); elements.add(currentElement); length += minElementCount; // incrementing length } return getFinalArray(frequencies, elements, length); }

private static int[] getFinalArray(List<Integer> frequencies, List<Integer> elements, int length) { int[] finalArray = new int[length]; int idx = 0; // array index for (int i = 0; i < elements.size(); i++) { int element = elements.get(i); int elementCount = frequencies.get(i); for (int j = 0; j < elementCount; j++) { finalArray[idx] = element; idx++; } } return finalArray; }

Return 在所有矩阵行中具有重复元素的数组

Return array with common elements in all matrix row-s with repetition

java

arrays

methods

integer

matrix