행 방식으로 정렬 된 행렬에서 가장 작은 정수를 나타내는 행 찾기
최근 Java 전화 인터뷰에서이 질문을 받았습니다.
다음 속성을 가진 NxN 이진 (0-1) 행렬이 제공됩니다.
- 각 행이 정렬됩니다 (0 시퀀스 다음에 1 시퀀스).
- 모든 행은 부호없는 정수 (비트를 읽음)를 나타냅니다.
- 각 행은 고유합니다.
예:
0 1 1
1 1 1
0 0 1
각 행의 비트 값이 정렬되고 행은 정수 3, 7 및 1을 나타냅니다.
가장 작은 정수를 나타내는 행을 찾습니다. 위의 예에서 답은 정수 1을 나타내는 행 3입니다.
나는 2 차 복잡성의 무차별 한 힘으로 시작했습니다. 면접관은 내가 분류 된 재산을 이용하지 않는다고 대답했다.
많은 생각을 한 후 각 행에서 이진 검색을 사용했고 O (nlogn)에 도달했습니다. 그는 내가 더 나아질 수 있는지 물었다. 많이 생각했지만 개선하지 못했습니다.
누구든지 그것을 자극하는 것에 대한 조언을 줄 수 있다면 감사하겠습니다.
또 다른 예:
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
답은 정수 0을 나타내는 행 3입니다.
행 1부터 시작합니다 1. 첫 번째를 칠 때까지 오른쪽으로 이동합니다 . 그런 다음 2 행으로 이동하되 동일한 열에 남아있는 상태에서 1. 이것을 반복하십시오. 마지막으로 오른 행이 답입니다.
이것은 O (N + M) 솔루션입니다 (NxM 행렬의 경우, 또는 질문에서 주어진 정사각형 NxN 행렬의 경우 O (N)).
귀하의 예를 사용하여 :
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
.'통과 경로를 나타냅니다 여기에 S :
. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .
이 솔루션은 NxM 행렬에 대해 최악의 경우 O (N + M) 효율성을 유지하면서 정사각형이 아닌 행렬에서 작동합니다.
왜 이것이 작동합니까? 숫자가 정렬된다는 보장은 모든 행이 일련의 0 다음에 일련의 1이 이어진다는 것을 의미합니다. 따라서 행의 크기는 1에 도달하기 전에 얼마나 오른쪽으로 갈 수 있는지와 동일합니다. 따라서 행이 0을 따라가는 것만으로 더 멀리 갈 수 있다면 이전에 처리 한 것보다 더 길어야합니다.
Python 코드 :
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
ans, j = 0, 0
for i, row in enumerate(li):
while j < len(row) and row[j] == 0:
j += 1
ans = i
print "Row", ans+1, "".join(map(str, li[ans]))
또한 항상 정사각형 NxN 행렬과 별개의 행을 함께 갖는 제약으로 인해 더 간단한 솔루션이 있습니다. 함께 그들은 가장 낮은 값을 가진 행이 0 0 ... 0 1또는 일 것임을 의미합니다 0 0 ... 0 0. 이는 행렬에 N + 1 개의 가능한 숫자가 표시되므로 "누락 된"숫자는 0 (이 경우 표시되는 가장 작은 값은 1)이거나 다른 것 (가장 작은 값은 0)이기 때문입니다.
이 지식을 바탕으로 오른쪽에서 두 번째 열에서 0을 확인합니다. 하나를 찾으면 오른쪽을보고 다른 0이 포함되어 있으면 답을 얻습니다 (a로 끝나는 행은 하나만있을 수 있음 0). 그렇지 않으면 열에서 다른 0을 계속 검색합니다. 다른 0을 찾지 못하면 처음 찾은 행이 찾고있는 행이었습니다 (로 끝나는 행이 하나만있을 수 있고 다음으로 끝나는 행 01이 없기 때문에 00, 이것은 가장 작습니다).
Python 코드 :
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
for i, row in enumerate(li):
if row[-2] == 0:
ans = i
if row[-1] == 0:
break
print "Row", ans+1, "".join(map(str, li[ans]))
이 솔루션은 O (N)에서 최소한의 어려움으로 질문에 답하지만, 정사각형이 아닌 NxM 행렬 또는 고유하지 않은 숫자를 처리하도록 일반화하면 최악의 경우 효율성 O (N ^ 2)가됩니다. 개인적으로 첫 번째 솔루션을 선호합니다.
가장 낮은 숫자는 0 또는 1이어야합니다 (중복이없고 행이 정렬되기 때문). ti가 0을 포함하면 가장 낮은 숫자는 0이고 그렇지 않으면 가장 낮은 숫자는 1입니다.
편집 - 설명
에 N제약이있는 행 당신은 최대있을 수 물리게 N+1고유 한 값.
따라서 적어도 0 또는 1이 행렬에 있어야합니다 ....
편집 2-알고리즘
//assuming the matrix is 0 indexed base
for i = 0...N-1
if M[i][N-1] == 0
return "Value is 0 in row i";
for i = 0...N-1
if M[i][N-2] == 0
return "Value is 1 in row i";
//because of the explanation above the flow will never reach here.
숫자가 고유하고 숫자가 정렬되어 있기 때문에 N의 값에 대해 가장 작은 숫자는 [0 (N-1 회) 뒤에 1] 또는 0 (N 회) 형식이 될 수 있음이 분명합니다. .
예를 들어 N = 4 인 경우 가장 작은 숫자는 0001 또는 0000이 될 수 있습니다.
즉, HAS를 찾고자하는 숫자의 마지막 두 번째 숫자는 0입니다. 마지막 숫자는 0 또는 1이 될 수 있습니다.
이 문제는 배열에서 이러한 패턴을 찾는 것으로 줄어들며, 간단한 for 루프를 사용하여 수행 할 수 있습니다.
int rowNum = -1;
for(int i=0;i<N;i++)
{
if(arr[i][N-2]==0) //Second last digit is 0. Hence the number could be min.
{
rowNum = i;
if(arr[i][N-1]==1) // If number of the form 0001 was found, keep looking for 0000
{
continue;
}
else
//If number of the form 0000 was found, exit.
//No other number can be lesser than 0000
{
break;
}
}
}
return rowNum;
이 알고리즘은 복잡성 O (n)
최대 개수가 0 인 행을 찾으려고합니다.
- 시작
arr[0][0] - 이면
0오른쪽에있는 요소를 확인하십시오arr[0][1]. - 그렇지 않은 경우
0해당 행을 건너 뛰고 현재 요소 아래 다음 행의 요소에서 확인을 시작합니다.
마지막 행 / 마지막 열을지나거나 모두 0이있는 행을 찾을 때까지 계속하십시오.
연산:
i = 0
j = 0
answer = 0
# continue till i is a valid index.
while(i<N)
# continue till j is valid index and ele is 0.
while(j < N AND arr[i][j] == 0)
# move towards right.
j++
#update answer.
answer = i
# found a row with all zeros.
if(j == N)
break all loops.
end-if
end-while
# skip current row..continue on next row.
i++
end-while
print answer
이러한 복잡성은 O(N+N)인 O(N), 즉 직선이다.
똑같은 트릭을 사용하는 관련 질문
정렬 된 행렬에서 효율적으로 검색하는 방법은 무엇입니까?
Start at the top-left.
The first row is the best row so far.
Repeat until you reach the bottom:
If you're not already over a 1:
Go right until you find a 1.
This row is the best row so far.
Go down one row.
Report the best row that was found.
You never go up or left - you only go down (n-1) times and right no more than (n-1) times, making this O(n). This exploits the sortedness by realizing that you never have to go left to check for a 1 - if there is a 1 somewhere to the left, then there is also a 1 in the current spot (and thus the number in this row is at least as big as the one in the previous row).
Since the bits in each row are sorted, once you have found a 1 bit, all bits to the right must be 1 too. In other words, the array only stores values of the form 2^n-1.
So the answer is the row with the most zero entries is the smallest.
However, since only 2**m-1 entries can be present, and there are n of those, and no two are the same we can deduce more - for any N there are N+1 such values. So either 0 or 1 must be present as we know there are no duplicates.
So look for an empty row (which is hte only one with rightmost column zero). If you don't find it, the answer is 1, else it's 0.
O(N)
How about looping each line in reverse order and checking where the 1s end and the zeroes start?
In fact it is guaranteed that in NxN, the worst case is that 0 won't be there. So you can just check the last 2 entries of each row. Which makes it linear.
Since my explanation was not understood, here it is in somewhat pseudo code:
int lowestRow = -1;
for (k = 0; k < array.length; k ++) {
byte[] row = array[k];
if (row[row.length - 1] == 0) {
lowestRow = k;
break;
}
if (row[row.length - 2] == 0) {
lowestRow = k;
//possibly look for all-zeroes, so not breaking
}
}
You have to start with the last column, and check if the sum of the element is N-1, once you have found the column with the sum = N-1 search the column containing a 0 and this is the one you are looking for...
An optimised version of @codaddict
int best = N;
int answer = -1;
for(int i=0;i<N;i++)
for(int j=0;j<best;j++)
if (arr[i][j] != 0) {
best = j;
answer = i;
}
The inner loops stops as soon as it determines this row won't be the better than the current answer. This could cut out alot of searching down rows which are longer than the best answer so far.
Find which row has the first non zero value in the furthest column. If it is binary, with the MSB on the left, and the LSB on the right the answer is the row that starts with the most zeros.
I would add this as a comment to Jeremy's answer if i could, because his solution is mostly correct. Also, I like the approach. In many instances it will be MUCH faster than other answers. There is a possible problem. If "Each row is sorted." does not mean that all ones are shifted to the right, but has some other implication(I can think of a couple of implications. I would need more from the individual asking the question). One problem...what about 0011 and 0010. Rows are sorted could mean that the algorithm you are implementing is already used. The algorithm specified in his answer cannot distinguish between the two. I would store the index of both answers in an array. If array length is 1 then you have a solution, otherwise you need to recurse further...just a thought. If anyone reads this that can post comments on others posts please reference this in a comment to his post. It is a serious problem, and it would be upsetting to have a technically incorrect answer get the check. If my comment is added I will delete my answer completely.
The smallest number can be 0 which looks like (0000...0000) or 1 which looks like (0000...0001).
Every larger number looks like (xxxx...xx11). So you should check the next to last digit in every row. If it is 0 then check if the last digit is 0. If it is it is the smallest number. If not, then remember the row number and continue looking for row with 0 on the next to last digit. If you find it, this will be the smallest number. If not, the first found number is smallest one.
This is the solution with N+1 steps (worst case scenario) which is O(N) complexity.
I don't know if it's admitted, but if it's sorted don't you need just to convert each row to decimal number and choose the row with the lower one. example:
[0111] -> 7
[0011] -> 3
[0000] -> 0
[0001] -> 1
The solution is the row with value 0. OR?
I have written a O(n) algorithm, similar to what has been stated above, we start from top-left corner and work downwards:
a = [
[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]
]
a2 = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 0, 0, 1],
[1, 1, 1, 1]
]
def search(a):
n = len(a)
c = 0
r = 0
best_row = 0
while c<n and r<n:
if a[r][c] == 0:
c += 1
else:
best_row = r
r += 1
if c==n : best_row = r
print( " best row: %d" % best_row )
search( a )
search( a2 )
'Programing' 카테고리의 다른 글
| SQL 덤프에서 데이터베이스를 복원하는 동안 바이너리 모드 활성화 (0) | 2020.11.16 |
|---|---|
| SQL에서 테이블 크기를 찾는 방법은 무엇입니까? (0) | 2020.11.16 |
| 전체 색조 변경-iOS7 / iOS8 (0) | 2020.11.16 |
| Swift를 사용하여 iOS 10에서 전화를 거는 방법은 무엇입니까? (0) | 2020.11.16 |
| Amazon MWS-계산 된 요청 서명이 제공된 서명과 일치하지 않습니다. (0) | 2020.11.16 |