There can be multiple ways to do this.. obviously sorting gives you o(nlogn). another approach of hashtable gives o(n) and here is another approach: 1. maintaining array of size N, initialized to 0. Say B 2. for(i=0;i<N;i++) { B[a[i]]++;} 3. Output all values with B[i] >= 1 , which gives unique elements only.
In your last approach, watch out for arbitrarily large values. What would 'N' be? By the way, 'for' loop there should be for 'n', which is the size of array 'a'. A simple array like {20, 5, 123456789} would kill your memory. Hashing approach would be great if we've some idea on nature of the array contents. Here's a method of O(n logn) again. Parse through each entry in the array and insert into a BST (Binary Search Tree). Ignore duplicate entries and hence gives unique elements when done in-traversal later. However, worst-case shoots to O(n^2) if the distribution is skewed.
Regards, Channa
On Oct 30, 2007 5:01 AM, MD <madhu.da...@gmail.com> wrote:
> There can be multiple ways to do this.. obviously sorting gives you > o(nlogn). > another approach of hashtable gives o(n) > and here is another approach: > 1. maintaining array of size N, initialized to 0. Say B > 2. for(i=0;i<N;i++) { B[a[i]]++;} > 3. Output all values with B[i] >= 1 , which gives unique elements > only.
i think if array of n elements is given and to make a heap out of it we need O(n) space. heap sort will surely take constant amount of auxially space if heap is already build.
No, it is not. Read carefully the article on Wikipedia. There is a very detailed explanation of the algorithm. Heap is build in an array being sorted. It's the strongest feature of the algorithm.
On Nov 9, 4:51 pm, "Pramod Negi" <negi.1...@gmail.com> wrote:
> i think if array of n elements is given and to make a heap out of it we need > O(n) space. > heap sort will surely take constant amount of auxially space if heap is > already build.
Heap sort has a function heapify which will build the heap. If you
just modify this heapify algorithm to eliminate the repeated elemenst
it will work in O(nLogn).
Also this will work for any number of repeated elements. you can find
this algo in hte Design analysis and algorithms by Corment in Chapter
7 : heap Sort.
I think this method will solve the problem:
1). first, sort the linear array using quick sort method, it will take
n(logn) time
2).second, scan the sorted linear array:
Array[nLen] //sorted data Array.
T tSameData;
int iNum;
int i, j, k, iLast = nLen; //nLen is the length of the array.
for (i=0; i<iLast; i++)
{
tSameData = Array[i];
j = i;
while (Array[j+1] == tSameData) j++;
if (j > i)
{
iNum = j - i;
for(k=iLast-1, i=i+1; k>iLast-1-iNum; k--, i++)
{
Array[i] = Array[k];
}
iLast -= iNum;
}
I think this method will solve the problem:
1). first, sort the linear array using quick sort method, it will take
O(n(logn)) time
2).second, scan the sorted linear array:
Array[nLen] //sorted data Array.
T tSameData;
int iNum;
int i, j, k, iLast = nLen; //nLen is the length of the array.
for (i=0; i<iLast; i++)
{
tSameData = Array[i];
j = i;
while (Array[j+1] == tSameData) j++;
if (j > i)
{
iNum = j - i;
for(k=iLast-1, i=i+1; k>iLast-1-iNum; k--, i++)
{
Array[i] = Array[k];
}
iLast -= iNum;
}
}
nLen = iLast;
because the same elements are not more than two, so the time spent
will be O(n)
Quicksort has an _average_ time of O(n log n) for random data, but it
can degenerate to O(n^2) for certain initial orderings. Thus, your
statement that it will take O(n log n) time is not justified. That is
why it has been suggested to use a heapsort or mergesort, both of
which are O(n log n).
Dave
On Dec 20, 8:02 pm, Bookpet <lid...@gmail.com> wrote:
> I think this method will solve the problem:
> 1). first, sort the linear array using quick sort method, it will take
> n(logn) time
> 2).second, scan the sorted linear array:
> Array[nLen] //sorted data Array.
> T tSameData;
> int iNum;
> int i, j, k, iLast = nLen; //nLen is the length of the array.
> for (i=0; i<iLast; i++)
> {
> tSameData = Array[i];
> j = i;
> while (Array[j+1] == tSameData) j++;
> if (j > i)
> {
> iNum = j - i;
> for(k=iLast-1, i=i+1; k>iLast-1-iNum; k--, i++)
> {
> Array[i] = Array[k];
> }
> iLast -= iNum;
> }}
|
