You are given an array A of n distinct integers, and an integer k such that 1<=k

Question

You are given an array A of n distinct integers, and an integer k such that 1<=k<=n. The square distance between a pair of integers x, y is defined as the quantity (x-y)^2. What I am trying to do is design an O(n) time algorithm to find k elements in A with the smallest square distance to the median (for example: the element of rank n/2 in A). For instance, if A=[9,5,-3,1,-2] and k=2, then the median element is 1 and the 2 elements in A with the smallest square distance to the median are {1,-2}. If k=3 then you can output either {1,-2,-3} pr {1,-2,5}

Explanation / Answer

I'm guessing you were already taught a linear selection algorithm. If not you can get it from wikipedia: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Use the selection algorithm to find the median. Make a list B consisting of the square distance to the median for each element in A. Use the selection algorithm to find the elements of rank 1, 2, ..., k in B. For each of these elements of B, get the corresponding element in A, and you're done.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.