요소 목록을 보면, 어떤 키로 요소를 그룹화하는 가장 효율적인 방법은 무엇입니까?목록의 요소를 효율적으로 그룹화
예를 들어 입력이 {a,c,a,b,c,b,b} 인 경우 유효한 출력은 {a,a,b,b,b,c,c} 또는 {b,b,b,c,c,a,a}이 될 수 있습니다.
분명히 키의 유형이 주문을 관찰하면 정렬 알고리즘을 사용하여 O(nlogn)의 복잡성을 제공 할 수 있습니다.
그러나 키는 동등 함만 비교할 수 있지만 순서는 비교할 수 없습니다. 예를 들어, typeof(dog) != typeof(cat)이지만 typeof(dog) < typeof(cat)인지 묻는 것은 의미가 없습니다.
물론 주문을 강제 할 수 있지만 (예 : obj.GetType().ToString() 및 어휘 순서 사용) 엄격한 순서가 필요하지 않기 때문에 (그룹화 만) 정렬보다 효율적인 방법이 있는지 궁금합니다.
나는 것 정렬되지 않은 연결리스트와, (의사 코드)이 같은 점을 삽입하기위한 해시 맵 사용
function group_sort(unsorted_list)
node_map = new hash_map
sorted_list = new linked_list
foreach node in unsorted_list
last_node = node_map.get(type_of(node))
if last_node found
sorted_list.insert_after(last_node,node)
else
sorted_list.append(node)
node_map.add(type_of(node),node)
delete node_map
return sorted_list
해시지도 조회 및 삽입 주로 O (1)과 해시 맵 삽입입니다 데이터에 따라 희귀 할 수도 있습니다. 링크 된 목록 삽입은 항상 O (1)입니다. 어떤 기능을 거의 O (n), 확실히 O (nlogn)로 만듭니다.
좋은 아이디어. 그러나 목록 삽입은 doubley-linked 목록으로 구현 된 경우에만 O (1)입니다. 기본 저장소가 배열 인 경우 자주 사용되는 구현 (예 : C# 용 ArrayList, Java 용 ArrayList
@MikeM : 배열 기반 목록의 중간에 요소 *를 삽입하는 것은 O (n)이지만 Fabel이 여기 에서처럼 끝에 추가하는 것은 O (1) (상각)입니다. 또한 단일 연결 목록의 앞에 삽입하는 것은 O (1)입니다. –
내 예제는 중간과 끝에 모두 삽입합니다. 둘 다 O (1)입니다. 그리고 분명히 말하자면, 배열이 아닌 연결된 목록을 말하고 있습니다. 정렬을 위해 배열을 사용하는 것은 매우 비효율적이며이 함수를 O (n2)로 만듭니다. – Fabel
당신은이 multiset
당신은 얼마나 키가 않습니다에 각 항목을 삽입 할 수 있을까? O (n) 또는 훨씬 작습니까? –
"적절한 위치에"그룹화를 원하거나 요소를 복사하고 다른 정렬 된 목록을 만드는 것이 좋습니다. –
@OhadEytan 키의 수는 다양하지만 대개 1에 가깝거나 n에 가깝습니다. 이 작업은 많은 입력에서 수행되므로 "적절한"알고리즘을 선호합니다. – MikeM