1
행렬에 관한 질문이 있습니다.요구 사항에 따른 행렬 위치 찾기
세그먼트 및 행렬 목록이 있습니다. 모든 세그먼트에는 이름, 시작 또는 끝점 및 시작점과 끝점이 행렬의 행 또는 열을 나타내는 경우 설명하는 값이 있습니다.
동일한 이름을 가진 세그먼트가 두 개 이상있을 수 있지만 (시작점과 종점이 다릅니다).
이제 이름 목록 (a, b, c)이 있습니다.
이 작업은 위치가 인 모든 행렬 위치 (x, y)를 목록의 이름이있는 모든 세그먼트의 범위 (시작 및 끝점)로 찾는 것입니다.
금식 방법은 무엇입니까?
KV- 다이어그램에서 논리 표현식의 위치를 찾으려면이 코드가 필요합니다.
처음에는 동일하게 채워진 행을 "압축"하고, 마찬가지로 열을 압축하면 속도가 빨라질 수 있습니다. 이것은 모든 세그먼트의 수직 종단점을 정렬 한 다음, 컬럼에 대해 동일한 종점을 사용하여 최대 2m x 2m 크기의 행렬을 남겨두고 O (m log m) 시간에 수행 할 수 있습니다. m이 세그먼트 (segment)의 수의 경우. (각 이름은 많은 세그먼트를 기술 할 수 있기 때문에 알고리즘의 시간 복잡도에도 "m"이 필요하다고 생각합니다.) –
@j_random_hacker 각 열과 각 행에 대해 수행해야하므로 쉽지 않습니다. 간격에 대한 차원. 동일한 이름의 세그먼트가 겹치지 않으면 세그먼트 수는 중요하지 않습니다. 이는 이름 당 최대 * * 세그먼트를 의미하지만 각 세그먼트는 하나의 셀만 포함합니다. – maraca
당신은 겹치지 않는 이름들에 대해 당신이 맞습니다. 당신의 시간 복잡성을 필요로하지 않는다는 것을 의미합니다, 미안합니다. 어쩌면 내가 잘 설명하지는 않았지만 동일한 열의 수평 간격과 동일한 행의 수직 간격을 압축하면 실제로 r과 c를 제거 할 수 있습니다. 압축 간격마다 원래 크기 (수) 행렬의 각 셀은 원래 행렬의 * rectangle *에 해당합니다 (모든 셀은 알고리즘에 의해 동일한 수를 수신합니다). –