要求:复杂度为O(n)
问题分析:如果存在i,那么i有且仅有一个.
算法:
(1)寻找这个可能存在的i.
从a[1][1]出发,判断当前元素是否为0.
如果不是
向右前进,直到越界,此时1就是{wy}可能存在的解.
如果a[1][k]==0
从a[k][k]出发,判断当前元素是否为1.
如果不是
向下前进,直到越界,此时k就是{wy}可能存在的解.
如果a[k][m]==1
从a[m][m]向右哦出发,重复上述步骤,直到越界.
复杂度O(n).
(2)验证
验证i行和i列的共2n-1个元素是否满足条件.
复杂度O(2n)
总的复杂度O(3n)
算法2:
这个问题可以换个角度理解,可以图来表示.
矩阵直接看作邻接举证.
对于非1，的数据都把他看成是0（即不相连).（题目没有说有没有，除1，0外的数据）
问题可以转化为:
在无环有向图中，找一个顶点，其出度问 n-1，入度为0.
一次判断2个顶点，A，B ，
（1）若A到B，且B不到A，删除A，B，保留A；同理,反过来，保留B
（2）若A,B有边连接，删除A，B
（3）若A,B互不连接，删除A，B
问题分析:如果存在i,那么i有且仅有一个.
算法:
(1)寻找这个可能存在的i.
从a[1][1]出发,判断当前元素是否为0.
如果不是
向右前进,直到越界,此时1就是{wy}可能存在的解.
如果a[1][k]==0
从a[k][k]出发,判断当前元素是否为1.
如果不是
向下前进,直到越界,此时k就是{wy}可能存在的解.
如果a[k][m]==1
从a[m][m]向右哦出发,重复上述步骤,直到越界.
复杂度O(n).
(2)验证
验证i行和i列的共2n-1个元素是否满足条件.
复杂度O(2n)
总的复杂度O(3n)
算法2:
这个问题可以换个角度理解,可以图来表示.
矩阵直接看作邻接举证.
对于非1，的数据都把他看成是0（即不相连).（题目没有说有没有，除1，0外的数据）
问题可以转化为:
在无环有向图中，找一个顶点，其出度问 n-1，入度为0.
一次判断2个顶点，A，B ，
（1）若A到B，且B不到A，删除A，B，保留A；同理,反过来，保留B
（2）若A,B有边连接，删除A，B
（3）若A,B互不连接，删除A，B
