对于一个n*n的矩阵，其中只包含有0,1两种元素且，所有的0都在1之前，请找出矩阵中0最多的一行。(Given an N-by-N matrix of 0s and 1s such that in each row no 0 comes before a 1, find the row with the most 0s in O(N) time.)
初看这题，想到的算法就是每一行都设置一个计数器，记录每行的0的个数，然后找出最大值即可(暴力解法)。
算法实现：
int* find_the_longest_row_force(int **a, int n)
{
int* res = new int[2];
res[0] = res[1] = -1;
for(int i=0; i<n; i++)
{
int max = 0;
for(int j=0;j<n;j++)
{
if(a[i][j] == 0)
max++;
}
if(max > res[1] && max!=0)
{
res[1] = max;
res[0] = i+1;
}
}
if(res[0] == -1)
res[1] = -1;
return res;
}
算法中有两层循环，因此算法的时间复杂度为o(n^2)。这样的算法是否还能改进呢？呵呵，当然可以。
首先由于矩阵中只含有0和1两个元素，且0在1之前，因此每一行都是排好序的，为此每行都使用二分查找，找到每行的最后一个0所在的位置，这个位置即为每行0的长度，如此循环查找n行，即可得到最长的一行的位置以及相应的0的长度。
算法实现
int* find_the_longest_row_search(int** a, int n)
{
int* res = new int[2];
res[0] = res[1] = -1;
for(int i=0; i<n; i++)
{
int low = 0;
int high = n-1;
int temp_loc = -1;
while(low <= high)
{
int mid = (low + high)/2;
if(a[i][mid] > 0)
high = mid -1;
else
{
if(mid > temp_loc)
temp_loc = mid;
low = mid + 1;
}
}
if(temp_loc > res[1])
{
res[1] = temp_loc;
res[0] = i+1;
}
}
if(res[0] != -1)
res[1] = res[1]+1;
return res;
}
上述算法实现的过程中，有一个循环，循环里面运行的是二分查找，时间复杂度为O(logn)，总共循环n次，因此总的算法的时间复杂度为O(nlogn)。与暴力算法相比，有了一定的提高。那这是不是最优的算法呢？
其实是有的，仔细想想，我们对每一行都进行二分查找似乎是多余的，比如说第一行的0的长度为10，那么我只要看第二行在10的位置是否为0，如果不为0，则这一行的0的个数就小于第一个行，如果大于0，那就继续在这行往后查找0。由此可得一个新的算法。
首先从左上角的第一个元素开始查看，如果为0，则向右查看，否则向下查看，如此循环，直到到达矩阵的边界为止。
算法实现：
int* find_the_longest_row_0(int** a, int n)
{
int* res = new int[2];
res[0]=-1;
res[1] =-1;
int i=0,j=0;
while (i<n && j<n)
{
if(a[i][j] == 0)
{
j++;
res[0] = i+1;
}
else
{
i++;
}
}
if(res[0] != -1)
res[1] = j;
return res;
}
上述算法实现的过程中，从矩阵的左上角已知查询到矩阵的右下角，中途只能往右或者往下查询，因此最多查询2n次即可找到含有0元素最多的行。为此算法的时间复杂度为O(n)。
测试代码：
#include <iostream>
#include<stdlib.h>
#include <time.h>
#include <string>
using namespace std;
int* find_the_longest_row_force(int **a, int n);
int* find_the_longest_row_search(int** a, int n);
int** Create_matrix(const int n);
void print(int** a, const int n);
int* find_the_longest_row_0(int** a, int n);
void main()
{
int n;
cout<<"Input the n: (exit 0)";
cin>>n;
while(n>0)
{
int** a = Create_matrix(n);
print(a,n);
const string name[3] = {"Force","Search","Best"};
int* (*(p[3]))(int**,int) = {find_the_longest_row_force,find_the_longest_row_search,find_the_longest_row_0};
int* res;
for(int i=0; i<3; i++)
{
res = p[i](a,n);
cout<<name[i]<<": "<<endl;
cout<<"The longest row is :"<<res[0]<<endl
<<"The length is :"<<res[1]<<endl;
}
delete[] res;
for(int i=0; i<n; i++)
delete[] a[i];
cout<<"Input the n: (exit 0)";
cin>>n;
}
}
辅助函数
int** Create_matrix(const int n)
{
int** a = new int*[n];
for(int i=0; i<n; i++)
{
a[i] = new int[n];
srand(i);
int index = rand()%n;
for(int j=0; j<n; j++)
{
if(j<index)
a[i][j] = 0;
else
a[i][j] = 1;
}
}
return a;
}
void print(int** a, const int n)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
上述算法优化的过程中发现，在设计一个问题的解题算法时，可以先设计出一个暴力算法，然后再暴力算法的基础上看是否存在可以改进的地方(本题主要的改进就是0这个元素的位置查询方式)。对本题而言，主要耗时就在0的位置的查询，第一中方法是挨个挨行的查询，其中存在较多的冗余，第二种方法减少了没有必要的查询，使用了二分查找，虽说在每行查询的时间减少了，但是由于没有充分利用上一次查询的信息，造成了一定的冗余查询。最后一种方法充分利用了上一行查询的信息，使得查询的效率大幅度提高。