Vishal
BAN USERIf numbers are not in any specific range, I think the solution would be through Hashtable. But, if the numbers are in range 1 to n where n is the size of array, it could be done in constant space and O(n) time.
Logic:
//keep flipping the sign of numbers
for (int i=0; i<n; i++) {
arr[ Math.abs(arr[i]) ] = - arr[ Math.abs(arr[i]) ];
}
//odd numbers will be the negative numbers in array
for(int i=0; i<n; i++) {
if(arr[ Math.abs(arr[i]) ] < 0)
System.out.println(Math.abs(arr[i]));
}
Code for Heap extractMin operation described by Jim:
NOTE- Median when n is odd is assumed to be at floor(n/2).
public static int extractMin(int [][] a) {
int result = a[0][0];
a[0][0] = Integer.MAX_VALUE;
int imin=0, jmin=0, icur=0, jcur=0;
while(true) {
if(icur+1 < a.length && a[icur+1][jcur] <= a[imin][jmin]) {
imin = icur+1;
jmin = jcur;
}
if(jcur+1 < a[0].length && a[icur][jcur+1] <= a[imin][jmin]) {
imin = icur;
jmin = jcur+1;
}
if(imin == icur && jmin == jcur) {
break;
}
else {
//System.out.println("Swapping "+imin+","+jmin+" with "+icur+","+jcur);
int temp = a[imin][jmin];
a[imin][jmin] = a[icur][jcur];
a[icur][jcur] = temp;
icur = imin;
jcur = jmin;
}
}
return result;
}
Result for:
1 2 3 101 102
4 5 6 103 104
7 8 9 105 106
10 11 107 108 109
12 50 110 111 112
is 12.
- Vishal January 29, 2014-Initialize 2 arrays, countRows, countCols to zero, to keep track of which rows and columns to make zero.
-Scan the given matrix for zeros and make countRows[i] and countCols[j] = 1
-In the second pass, just go through countRows and countCols, look for 1 and make the corresponding row and column 0.
Complexity: O(m x n)
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int a[][] = { {1,2,3,4} , {5,6,7,8} , {9,0,11,12} , {13,14,15,16}, {17,18,0,20} };
a = repZeros(a);
for(int i=0; i<a.length;i++)
System.out.println(Arrays.toString(a[i]));
}
public static int[][] repZeros(int a[][]) {
int countRows[] = new int[a.length];
int countCols[] = new int[a[0].length];
for(int i=0; i<countRows.length; i++)
countRows[i] = 0;
for(int j=0; j<countCols.length; j++)
countRows[j] = 0;
for(int i = 0; i<a.length; i++) {
for(int j=0; j<a[0].length; j++) {
if(a[i][j] == 0) {
countRows[i] = 1;
countCols[j] = 1;
}
}
}
for(int i=0; i<countRows.length; i++) {
if(countRows[i] == 1) {
for(int j=0;j<countCols.length; j++)
a[i][j] = 0;
}
}
for(int i=0; i<countCols.length; i++) {
if(countCols[i] == 1) {
for(int j=0;j<countRows.length; j++)
a[j][i] = 0;
}
}
return a;
}
}
RepMariaHobbs, Consultant at Adobe
Hi, I am Maria Hobbs from NewYork.Teach career development courses for designated areas. Develop, evaluate and revise course materials ...
snoqualmieseattle : Post this as an answer! :)
- Vishal February 23, 2014