5,323
edits
Parallel Algorithms: Difference between revisions
→Removing duplicates in an array
| Line 718: | Line 718: | ||
# Given array A of size n with entries 0 to n-1 | # Given array A of size n with entries 0 to n-1 | ||
# For each entry pardo | # For each entry pardo | ||
#* Write B[A[i]] == i | |||
#* Only one write will succeed for each unique A[i] | |||
#* Check if B[A[i]] == i | |||
===Compaction of an <math>n^2</math> array with <math>\leq n</math> elements in <math>O(\log n)</math> time=== | ===Compaction of an <math>n^2</math> array with <math>\leq n</math> elements in <math>O(\log n)</math> time=== | ||