주어진 부울 행렬을 행별로 정렬합니다. 최대 숫자가 1 인 행 반환

행렬 문제를 발견했지만 최적의 솔루션을 찾으려고했습니다. Problem statement는 질문 주제 그 자체입니다. 행이 정렬되기 때문에, 지금, 1 처음 나타나는 각 행에 이진 검색을 수행 생각하고 total number of columns minus index of 1st 1 것 (1)의 계산 : 는주어진 부울 행렬을 행별로 정렬합니다. 최대 숫자가 1 인 행 반환

Example 
Input matrix 

    0 1 1 1 
    0 0 1 1 
    1 1 1 1 // this row has maximum 1s 
    0 0 0 0 

Output: 2

내 솔루션 이하 더 참조.

이 작업은 O(m*logn)에서 이루어 지겠지만 선형 시간으로 수행 할 수 있는지에 대해서는 궁금합니다.

감사합니다.

출처

2013-07-26 roger_that

그 행렬을 정렬하는 방법 경우 여러 행을 찾을 수

단계 O 소요 행 현명한? '0111'>'0011'이 아닌가요? – Dukeling

내가 말할 때, 행렬은 줄 단위로 정렬되고 각 행은 오름차순으로 정렬됩니다. –

왜 좌상단에서 걸을까요? 첫 번째는 가장 좋은 행입니다. –

오른쪽 상단에서 커서를 시작하십시오. 각 행에서 마지막 행에 도달 할 때까지 왼쪽으로 1 단계 이동하십시오. 그런 다음 내려주세요. 당신이 내려와 커서가 0을 가리킨다면, 다시 내려 간다. 절대로 가지 마세요. 왼쪽으로 1 행이있는 행을 찾고 있으므로 오른쪽으로 볼 필요가 없습니다. 런타임은 O (n + m)입니다. 왜냐하면 모든 행을 거치면서 m 번씩 계단을 내려 가면서 총 n 개의 계단을 남겨두기 때문입니다. 말 그대로 코드를 변환하는 경우

bestrow = 0 
leftmost = matrix.width 

for i = matrix.height to 0: 
    row = matrix[i] 
    while row[leftmost - 1] == 1: 
     leftmost-- 
     bestrow = i 

return bestrow

, 모든 공의의의 매트릭스에 문제가 있거나 일부 행이있는 경우 모두 1 수 있습니다 : 여기 행렬이 목록의 목록입니다 가정, 일부 의사입니다. 이들은 다루기가 매우 쉽고, 의사 코드의 요점은 일반 알고리즘을 전달하는 것입니다.

출처

2013-07-26 05:28:31

이것은 좋은 해결책 인 것 같습니다. 좋은 :) –

이 문제의 해결 방법은 각 행의 요소 수와 열 수에 따라 다릅니다. 다음은 접근 방식입니다.

1 단계 : 당신은 우리가 적어도 하나의 일이있는 열을 발견 의미하는 진정한 때까지 간단한 각 열에있는 모든 요소에 진 & & 작업을한다. 이것은 n이 최대 열 수인 최대 n 단계를 취합니다.

2 단계 : 최대 열 수를 가진 행을 제공하는 열에서 위에서 아래로 검색하십시오. 이 m의 steps.where의 m의 최대 걸립니다 행 의 수는 그래서 전체가 (m + n)은 또한 동일한 속성을 가진 어떤

출처

2013-07-26 05:52:31

주어진 부울 행렬을 행별로 정렬합니다. 최대 숫자가 1 인 행 반환

답변

관련 문제