0.先晒图,在搞事
1.快速找到Target的区间
1)将【m】【n】分成若干块,
public boolean Find(int target, int [][] array) { int m = array[0].length; int n = array.length; int templen = m>=n ? m/n : n/m ; int templen2 = m>=n ? m%n : n%m ;//非整倍本体没有考虑 for (int i = 0; i < templen; i++) { if (getTag(target, array, n*i,n*(1+i))) { return true; } } return false; }
2)从左侧第一块开始依次,左上角开始沿对角线寻找target范围
private boolean getTag(int target, int[][] array, int staartLen,int endlen) { int fristIndex = 0; for(int i = staartLen;i<endlen;i++){ if(i>0) { if(target<array[i][i] && target>array[i-1][i-1]){ fristIndex = i; System.out.println("array[i][i]:"+array[i][i]+" array[i-1][i-1]:"+array[i-1][i-1]); break; } if(target == array[i][i]){ fristIndex = i; System.out.println("fristIndex:"+fristIndex); return true; } }else { if(target == array[i][i]){ return true; } } } }
3)从2)中i为原点先右上寻找target
思路:
向Y1正半轴,寻找直到Y1轴上的值小于target,
然后Y1不变,X1向正半轴方向寻找,
如此反复。。。。
for(int i = fristIndex;i>=0;i--){ if(array[i][fristIndex] == target ){ return array[i][fristIndex] == target; } if (array[i][fristIndex] < target) { break; } } int x =fristIndex, y = fristIndex; for (int i = fristIndex*2; i >= 0 && y>=0; i--) { System.out.println("x:"+x+" y:"+y); if (array[x][y]==target){ System.out.println("array[x][y]:"+array[x][y]); return true; } if (array[x][y]>target) { --y; }else if (array[x][y]<target){ ++x; } }
4)同理target可能出现在i的左下角,可以参考3),本题中没有涉及
5)完整代码
public boolean Find(int target, int [][] array) { int m = array[0].length; int n = array.length; int templen = m>=n ? m/n : n/m ; int templen2 = m>=n ? m%n : n%m ; for (int i = 0; i < templen; i++) { if (getTag(target, array, n*i,n*(1+i))) { return true; } } return false; } private boolean getTag(int target, int[][] array, int staartLen,int endlen) { int fristIndex = 0; for(int i = staartLen;i<endlen;i++){ if(i>0) { if(target<array[i][i] && target>array[i-1][i-1]){ fristIndex = i; System.out.println("array[i][i]:"+array[i][i]+" array[i-1][i-1]:"+array[i-1][i-1]); break; } if(target == array[i][i]){ fristIndex = i; System.out.println("fristIndex:"+fristIndex); return true; } }else { if(target == array[i][i]){ return true; } } } System.out.println("fristIndex:"+fristIndex+" staartLen:"+staartLen+" endlen:"+endlen); for(int i = fristIndex;i>=staartLen;i--){ if(array[fristIndex][i] == target ){ return array[fristIndex][i] == target; } if (array[fristIndex][i] < target) { break; } } for(int i = fristIndex;i>=0;i--){ if(array[i][fristIndex] == target ){ return array[i][fristIndex] == target; } if (array[i][fristIndex] < target) { break; } } int x =fristIndex, y = fristIndex; for (int i = fristIndex*2; i >= 0 && y>=0; i--) { System.out.println("x:"+x+" y:"+y); if (array[x][y]==target){ System.out.println("array[x][y]:"+array[x][y]); return true; } if (array[x][y]>target) { --y; }else if (array[x][y]<target){ ++x; } } return false; }
6)若有漏洞处,望大神,路过留笔。