Currently working on a method that takes a n*n matrix as input and returns an array consisting of all elements that are found in each sub-array. However, since I need it to also include duplicates etc, it's harder than I thought.
Googled the hell out of it, however, yet to find a solution which matches my criteria of repetition.
Currently I have this, which compares the element's of the first row with every other row and all their elements. If the counter gets to the length where it confirms that the element indeed is present in all rows, it adds it to the array. However, this has faults in it. First of all, since I create a set array in the beginning with the maximum possible length, it might return an array with non-needed 0's in it. And second, the duplicate part is not working correctly, struggling to implement a check there.
Examples of input/output that I need:
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;
}
EDIT: This is what I finally got together that fits my requirements and works flawlessly, with comments
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;
Grateful for help :)
CodePudding user response：
The most efficient way to solve this problem is by creating a histogram of frequencies for each nested array in the matrix (i.e. determine the number of occurrences for every element in the nested array).
Every histogram will be represented by a Map<Integer, Integer> (array element as a key, its occurrences as a value). To generate a histogram only a single pass through the array is needed. In the solution below this logic resides inside the getFrequencies() method.
After creating all histograms we have to merge them. In terms of set theory we are looking for an intersection of keys in all histograms. I.e. we need only those keys that appear at least once in every histogram and a value for each key will be the smallest in all histograms for that key. This logic is placed in the getCommonElements().
In order to create a merged histogram, we can pick any of the histograms (in the code below the first histogram is used frequencies.get(0).keySet()) and iterate over its keys. Then in the nested loop, for every key, we need to find the minimum value associated with that in every histogram in a list (reminder: that will be the smallest number of occurrences for the key).
At the same time, while merging histograms we can also find the length of the resulting array by adding all the minimal frequencies together. That small optimization will allow to avoid doing the second iteration over the merged map.
The last step required is to populate the resulting array commonElements with keys from the merged histogram. Value of every key denotes how many times it has to be placed in the resulting array.
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;
}
output
[1, 2, 2]
[1, 2]
Side note: don't violate the naming conventions, use camel-case for method and variable names.
Update
I've managed to implement a brute-force solution based on arrays and lists only as required.
The most important thing is that for this task you need two lists: one to store elements, another to store frequencies. Lists are bound together via indices. And these two lists are basically mimic a map, frankly saying a very inefficient one (but that's a requirement). Another possibility is to implement a class with two int fields that will represent the data for a common element, and then store the instances of this class in a single list. But in this case, the process of checking whether a particular element already exists in the list will be much more verbose.
The overall logic has some similarities with the solution above.
First, we need to pick a single array in the matrix (matrix[0]) and compare all its unique elements against the contents of all other arrays. Every element with non-zero frequency will be reflected in the list of elements and in the list of frequencies at the same index in both. And when the resulting array is being created the code relies on the corresponding indices in these lists.
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;
}