二维数组查找K（Go语言）

原作者: [db:作者] 来自: [db:来源] 收藏邀请

问题：二维数组行列递增排列，求找target位置

思路1：从左下方依次遍历

func findKey(arr [][]int, target int)(int, int){
    col := len(arr)-1
    row := len(arr[0])-1
    i := 0
    for i<=row && col >=0 {
        if (arr[col][i] == target ){
            return col+1,i+1
        }else if arr[col][i]<target{
            i++
        }else{
            col--
        }
    }
    return -1,-1
}

更进一步找最小K的值

int min = a[0][0];
int minOfRows[rows];
 
for(i = 0; i < rows; i++)
    minOfRows[i] = 0;
 
minOfRows[0] = 1;
	
for(i = 1; i < k; i++)
{
    min = INT_MAX;
    for(j = 0; j < rows; j++)
    {
        if (minOfRows[j] < cols)
        {
            if(a[j][minOfRows[j]] < min)
            {
                min = a[j][minOfRows[j]];
                r = j;
            }
        }		
    }
    minOfRows[r]++;	
}

　　思路：

1）对整个数组进行k次扫描

2）每一次扫描都包每一行的最小元素进行比较，找出这次比较中的最小值 min，如果这次找出的元素师在第i行第j列，那么第i行下一次比较就从j+1开始（譬如说第一次扫描的最小值是0行的0列元素，那么第二次扫描第0行第0列元素就会被排除，第0行从第1列开始比较）

3）当第K次扫描后，所得的min就是整个数组的

有点不太确定，这个是否正确，等有时间，再看看