As described earlier, it can be done in O(n) independently of k.
1. Find the median, M: O(n)
2. Form a second array containing y(i) = abs(x(i) - M): O(n)
3. Find the kth smallest element of this array, K: O(n)
4. Scan the original array and locate the first k elements such that
abs(x(i) - M) <= K:
I agree time should be O(kn)
On Jan 26, 9:55 pm, Sharath Channahalli
wrote:
> a) Find the median - O(n)
> b) remove the element and again find the median
> c) conitnue b until you get k-1 elements
>
> time complexity - kO(n)
>
> On Wed, Jan 26, 2011 at 9:55 PM, ritu wrote:
>
> > solution is nice
a) Find the median - O(n)
b) remove the element and again find the median
c) conitnue b until you get k-1 elements
time complexity - kO(n)
On Wed, Jan 26, 2011 at 9:55 PM, ritu wrote:
>
> solution is nice!!but How to keep track of k closet numbers?
>
>
> On Jan 23, 9:22 pm, ritesh wrote:
> > 1
solution is nice!!but How to keep track of k closet numbers?
On Jan 23, 9:22 pm, ritesh wrote:
> 1.) find x= median in o(n)
> 2.) subtract x from each number of the array
> 3.) find the k smallest number using o(n) algrithm
>
> On Jan 21, 4:04 am, snehal jain wrote:
>
> > Given an unsorted arr
using selection algorithm ... http://en.wikipedia.org/wiki/Selection_algorithm
On Jan 24, 3:15 am, Anand wrote:
> How to find K smallest using O(n)
>
> On Sun, Jan 23, 2011 at 9:33 AM, Dave wrote:
> > @Ritesh: Very clever. In step 2 you should take the absolute value,
> > meaning that you need a
How to find K smallest using O(n)
On Sun, Jan 23, 2011 at 9:33 AM, Dave wrote:
> @Ritesh: Very clever. In step 2 you should take the absolute value,
> meaning that you need a copy of the original array in order to recover
> the closest numbers, or in step 3 you should find the k smallest
> absol
@Ritesh: Very clever. In step 2 you should take the absolute value,
meaning that you need a copy of the original array in order to recover
the closest numbers, or in step 3 you should find the k smallest
absolute values. It is more work, but still O(n), but then you don't
need the extra copy of the
1.) find x= median in o(n)
2.) subtract x from each number of the array
3.) find the k smallest number using o(n) algrithm
On Jan 21, 4:04 am, snehal jain wrote:
> Given an unsorted array A of n distinct numbers and an integer k where
> 1 <= k <= n, design an algorithm that finds the k numbers in
