무작위로 배열 채우기

Question

add()를 호출하여 배열이 임의의 빈 위치에 채워지는 데이터 구조를 만들려고합니다. 위치가 채워지면 다른 add()로 덮어 쓸 수 없습니다. remove (i)를 호출하면 A [i]의 위치가 해제됩니다. add() 및 remove() 호출은 섞일 수 있습니다.

제 생각에는 add()가 호출 될 때마다 임의로 0과 n-1 사이의 숫자를 생성하는 것이 었습니다. 비어 있으면 채 웁니다. 가득 찼 으면 빈 검색 주소가 나올 때까지 순차 검색을 수행하십시오. 그러나 두 가지 문제가 있습니다. 1) 배열이 대부분 꽉 찬 경우 O (n) 시간에 가까워집니다. 2) 무작위 선택이 균일하지 않습니다.

나의 두 번째 생각은 1에서 n-1까지 셔플을 사용하고이 순서대로 추가하는 것이지만 remove()는 지원하지 않습니다.

add() 및 remove()에 대한 지속적인 성능을 보장하는 방법을 구현할 수 있습니까?

Answer 1

빈 채워진 배열 위치에 대해 연결된 목록을 분리하여 보관할 수 있습니다. 0에서 (고려 된 링크리스트의 길이, 즉 채워지거나 비어있는) 랜덤을 생성하고 이것을 사용하여리스트에서 임의의 위치를 ​​선택하십시오. 이제 채워진 목록에서 요소를 선택한 다음 해당 항목을 삭제하고 빈 목록에 추가하십시오. 확실히 링크 된 목록의 순회는 O (연결된 목록의 길이) 시간이 걸리지 만 add() 또는 fill() 중 채워진 위치를 선택하는 문제는 제거됩니다.

Answer 2

배열을 채우려면 work_array[]이라고합시다. 두 개의 보조 배열 filled_positions[]과 empty_positions[]을 사용하고 work_array[]의 두 개의 카운터, num_filled 및 num_empty을 포함하여 filled_positions[] 및 empty_positions[]의 요소 수를 제공합니다. 배열이 0에서부터 인덱싱된다고 가정하면 처음에는 num_filled이 0이고 empty_positions[]은 0, 1, 2, ...에서 n - 1이고 num_empty은 n입니다.

• 는 임의의 위치에 요소를 추가하려면 :
  1. 은 임의의 숫자를 0 및 num_empty - 1,까지의 R를 생성합니다.
  2. 색인을 선택하십시오 i에서 empty_positions[r].
  3. 이 num_empty-1보다 작 으면 empty_positions[r]을 empty_positions[num_empty-1]으로 설정하십시오.
  4. 감소 num_empty.
  5. 세트 filled_positions[num_filled] ~ i.
  6. 증분 num_filled.
  7. work_array[i]에 요소를 채 웁니다.
임의 위치로부터 요소를 제거하는 방법 :
1. 난수를 0 및 num_filled - 1, R까지의 생성.
2. 색인을 선택하십시오 에서 filled_positions[r]을 선택하십시오.
3. 이 num_filled - 1보다 작 으면 filled_positions[r]을 filled_positions[num_filled-1]으로 설정하십시오.
4. 감소 num_filled.
5. 세트 empty_positions[num_empty]에서 i.
6. 증분 num_empty.

당신은 work_array_map[i] 달리 work_array[i] 채워진 경우 1과 0 인 상태 비트 work_array_map[]의 배열을 유지하도록 할 수있다. work_array_map[]을 사용하면 일정한 시간 내에 요소 이 채워 졌는지 여부를 알 수 있습니다.