2D 매트릭스에서 이진 검색

Question

이것은 숙제가 아니며, 답변이없는 웹 사이트에서 읽은 인터뷰 질문입니다. 나는 단지 나의 해결책을 검증하고있다.

질문 :

정렬 된 순서로 0과 1로 행렬을 감안할 때. 최대 1의 수로 행 인덱스를 리턴하는 알고리즘을 설계하십시오. 그 후 그는 행이 증가하는 순서로 정렬되고 일부는 감소하는 순서로 정렬된다는 질문을 수정했습니다.

O (행 * LogRows) 결과가 각 행에 대해 이진 검색을 적용 할 생각이지만, 그 또 다른 반복에서 다시 결과를 줄 것입니다 계산, 나는 줄일 생각입니다. 그 타이밍, 내가 해쉬 맵이나 사전에 반복하는 것을 추가하고, 그 수를 저장 한 후에 다시 반복하여 최대 행을 찾는다.

복잡성 측면에서 더 빠른 해결책이 있습니까? 아니면 내 접근 방식의 결함입니까?

Answer 1

첫 번째 색인 (오름차순) 또는 첫 번째 0 (내림차순) 색인을 얻은 후 왜 개수를 계산해야합니까? 행이 정렬되거나 오름차순으로 내림차순 인 경우 하나의 연산에서 수행 할 수 있습니다. 첫 번째 요소와 마지막 요소를 비교하십시오.

높은 수준의 의사 코드

: 당신은 당신이 첫 번째 (오름차순) 또는 첫번째 제로의 인덱스를 일단 사람을 계산해야합니까 (내림차순 왜

maxRow <- -1 
maxOnes <- -infinity 
For each row: 
    check if row is ascending or descending 
    do a binary search for the first 0 (if descending) or first 1 (if ascending) 
    use the above calculated index, and the length of the row to find number of ones in this row 
    if number of ones is more than maxOnes: 
    modify maxRow and maxOnes with the values of this line 
return maxRow 

이 O(#rows*log{size(row)})