gztyjz
BAN USERI have a O(n) method with O(1) space.
Since every element is not in its final position except first and last element, we can randomly pick one element at first, for example the second one(a2), record its posision(currentIndex) and do the following loop until a2 in its final position(currentIndex==2):
1. calculate which element should be in this currentIndex position
if currentIndex is even number, the element should be in this position is a1...an. We use currentIndex/2 to calculate the current position of this element(index)
if currentIndex is odd numver, the element should be in this position is b1...bn. we use (currentIndex-1)/2+n
2. swap arr[currentIndex] and arr[index].
3. record the current position of a2(currentIndex).
void DoChangeElement(int currentIndex, int * arr, int length)
{
if (length&1)
{
cout<<"Length must be even and big than 0."<<endl;
return;
}
if(length==1) return;
//loop until a2 is in its right position
while(currentIndex!=2)
{
//calculate the right element for this currentIndex
int index=0;
if(currentIndex&1) index=(currentIndex-1)/2+(length/2);
else index=currentIndex/2;
swap(arr[currentIndex],arr[index]);
currentIndex=index;
}
}
Assuming the matrix is int[m,n] a, you just need to check the elements in submatrix [1,1] to [m-2,n-2]. If a[i,j] is 0, then you set the edge of its col and row be 0. In this case a[0,j],a[m-1,j],a[i,0],a[i,n-1] be zero. After checking all elements then check the edge of the matrix, if a[i,0] and a[i,n-1] are both 0 then set all elements in row i be 0. Similarly if a[0,j] and a[m-1,j] are 0 then set all element in col j be 0.
- gztyjz March 23, 2012Before all this. You need 4 variables to record if elements in specific edge should be set to 0.
Ex:
1011
1111
1101
1111
First you need 4 variables, bool left=false,right=false,top=true (because a[0,1] is 0), bottom=false. Also set a[3,1] be 0 because a[0,1] is 0:
1011
1111
1101
1011
Then check sub-matrix from a[1,1] to a[3,3], finding a[2,2] is 0. So set a[0,2],a[3,2],a[2,0],a[3,0] be 0:
1001
1111
0100
1001
Now check the edges again and reset all cols and rows with edge be 0:
1001
1001
0000
1001
Finally check 4 variables again and reset edges:
0000
1001
0000
1001
Time: O(MN)
Space:O(1)