I have a given matrix called m and its dimensions are n by n and it contains whole numbers. I need to copy the numbers that appear just once to a new array called a.
I think the logic would be to have a for loop for each number in the matrix and compare it to every other number, but I don't know how to actually do that with code.
I can only use loops (no maps or such) and this is what I've come up with:
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 ;
}
}
}
It's probably not correct though.
CodePudding user response：
This is one of those problems you can just throw a HashMap at and it just does your job for you. You traverse the 2d array, use a HashMap to store each element with its occurence, then traverse the HashMap and add all elements with occurence 1 to a list. Then convert this list to an array, which is what you're required to return.
This has O(n*n) complexity, where n is one dimension of the square matrix 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);
}
}
CodePudding user response：
Loop through it again to see if there's any repeated one. Assuming you can use labels, the answer might look a bit like that:
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 * y] = currentNumber;
}
}
}
return a;
}
Not sure if it's the most efficient, but I think it will work. It's somewhat hard to form your final array without the help of Lists or such. Since the unassigned values will default to 0, any actual zero (i.e. it's "supposed" to be there based on the matrix) will be undetected if you look up the returned array. But if there's such limitations I imagine that it's not crucially important.
CodePudding user response：
It may be better to use a boolean array boolean[] dups to track duplicated numbers, so during the first pass this intermediate array is populated and the number of singles is counted.
Then create the resulting array of appropriate size, and if this array is not empty, in the second iteration over the dups copy the values marked as singles to the resulting array.
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;
}
Test:
int[][] mat = {
{2, 2, 3, 3},
{4, 2, 0, 3},
{5, 4, 2, 1}
};
System.out.println(Arrays.toString(getSingles(mat)));
Output(including debugging log):
singles = 3; [true, true, true, true, true, true, false, true, false, true, true, false]
[0, 5, 1]
CodePudding user response：
Your use of previous is merely an idea on the horizon. Remove it, and fill the one dimensional a. Finding duplicates with two nested for-loops would require n4 steps. However if you sort the array a, - order the values - which costs n² log n², you can find duplicates much faster.
Arrays.sort(a);
int previous = a[0];
for (int h = 1; h < a.length; h) {
if (a[h] == previous)...
previous = a[h];
...
It almost looks like this solution was already treated in class.
CodePudding user response：
It doesn't look good:
previous = m[i][j];
if (m[i][j] != previous) {
a[h] = m[i][j];
h ;
}
you assigned m[i][j] to previous and then you check if if (m[i][j] != previous)?
Are there any limitations in the task as to the range from which the numbers can come from?