Finding the same numbers in a matrix with some conditions
I have a programming problem. At some point, the question is simple. I wrote that the solution doesn't work very well. I want your opinion on this issue, how would you manage to solve this problem in "better" programming.
Question:
Write a program that will have an N * N input array. This array contains integers. You have to find how many different numbers exist with the following condition: Different number also:
A) Numbers that are the same but are consecutive. for example, 1 1 can be counted as one number because they are the same and next to each other.
B) (A) to be true, if you have for example number 1, then any Identical digits on the left, right, top and bottom also match.
eg
1 1 2 3
1 2 3 4
2 2 1 3
So there are 8 different numbers for the above. This is because in the array [0,0] [0, 1] and [1,0] can be viewed as one number, not 3 different ones. [1,1], [2,1] and therefore [2,0] are also the same numbers. So, as you can see on the last numbers, [1,1], [2,1] does indeed entail conditions, and then [2,0], [2,1] also entails conditions, but since [2 , 1] also implies c [1,1], so all [1,1], [2,1] and [2,0] are the same number.
My code:
public class matrix
{
public static void main(String[] args)
{
int[][] arr =
{
{1, 2, 3, 4},
{1, 1, 2, 4},
{5, 6, 2, 2},
};
for(int row = 0; row < arr.length; ++row)
{
for(int col = 0; col < arr[row].length; ++col)
{
//top
if(row!=0)
{
if((arr[row][col] == arr[row-1][col]) || (Math.abs(arr[row][col]) == arr[row-1][col]) || (arr[row][col] == Math.abs(arr[row-1][col])))
{
arr[row-1][col] = -arr[row-1][col];
}
}
//botom
if(row!=arr.length-1)
{
if(arr[row][col] == arr[row+1][col] || Math.abs(arr[row][col]) == arr[row+1][col] || arr[row][col] == Math.abs(arr[row+1][col]))
{
arr[row+1][col] = -arr[row+1][col];
}
}
//left
if(col!=0)
{
if(arr[row][col] == arr[row][col-1] || Math.abs(arr[row][col]) == arr[row][col-1] || arr[row][col] == Math.abs(arr[row][col-1]))
{
arr[row][col-1] = -arr[row][col-1];
}
}
//right
if(col!=arr[0].length-1)
{
if(arr[row][col] == arr[row][col+1] || Math.abs(arr[row][col]) == arr[row][col+1] || arr[row][col] == Math.abs(arr[row][col+1]))
{
arr[row][col+1] = -arr[row][col+1];
}
}
}
}
for(int row = 0; row < arr.length; ++row)
{
for(int col = 0; col < arr[row].length; ++col)
{
System.out.print(arr[row][col] + " ");
}
System.out.println();
}
}
}
My logic is to set the same numbers to negative and then just count only positive values to find different numbers.
I need a different algorithm that will give less Big-O complexity.
Thank.
source to share
If I understand your problem correctly, you can think of it as a graph problem by counting the number of connected components.
For example, make each entry in the matrix a vertex (labeled with a row column), so (0,0) is a vertex (with a value of 1). Then, two vertices are adjacent if they are directly above, below, right, or left of each other and have the same value. For example, (0,0) is adjacent to (0,1) because both have a value of 1. (0,1) is not adjacent to (0,2) because the first has a value of 1 and the second has a value of 2. Then you count the number connected components in your graphic. Each connected component is a "different" number.
There are many ways to quickly count the number of connected components. For example, start at the top (0,0) and search by breadth. Any vertices found are in the same component as (0,0). Then try again starting at any vertex that hasn't been found yet. The first Breadth First Search is linear time, but you will have to run it multiple times (assuming that the longer you run it faster than each run will be), so it is a little difficult to determine the exact asymptotic execution time. The size of your input is n ^ 2 (number of vertices). This will be no worse than n ^ 3 and probably much closer to n ^ 2 (remember that n ^ 2 means "linear in size to input").
source to share