This works for numbers with in 2^32 for 32-bit word length systems ..
int i=0;
for(int j=0;j0)
Array[j] is duplicate ..
else i |= (1< wrote:
> Sorting is fine but destroys the input, which often hurts, especially
> in version 2. Unless you use fancy probing techniques, number of
>
Sorting is fine but destroys the input, which often hurts, especially
in version 2. Unless you use fancy probing techniques, number of
comparisons is O(n).
If you're not sorting, then you need a "set" data structure of some
form. If the numbers are "small integers", an array of bits is good.
Set
that is what i said in above post. By portion or radix i mean : digit if
numbers are being sorted at radix 10.
On Wed, Aug 31, 2011 at 9:43 PM, Dave wrote:
> @Mohit: As I said, a radix sort does not use data comparisons. It
> extracts "digits" from the sort keys and uses the digits as
> subscri
@Mohit: As I said, a radix sort does not use data comparisons. It
extracts "digits" from the sort keys and uses the digits as
subscripts. Other than moving the data around, this is the only use
the radix sort makes of the sort keys.
Dave
On Aug 31, 11:06 am, mohit verma wrote:
> Is anything spec
Is anything specific about digits of numbers given in above question? If no
then as i said
Yeah coz we compare the radix part in radix sort , so can't say exactly we
are comparing the numbers (but portion of it)
On Wed, Aug 31, 2011 at 9:27 PM, Dave wrote:
> @Mohit: No. Radix sort on a fixed
@Mohit: No. Radix sort on a fixed data type is O(n) in time, and uses
no data comparisons.
Dave
On Aug 31, 10:45 am, mohit verma wrote:
> @ dave- commplexity of radix sort is >= O(n log n). so better use heap sort.
>
>
>
>
>
> On Wed, Aug 31, 2011 at 4:07 PM, Dave wrote:
> > @Bharatkumar: You'v
>=O(nlog n) for random k.
On Wed, Aug 31, 2011 at 9:15 PM, mohit verma wrote:
> @ dave- commplexity of radix sort is >= O(n log n). so better use heap
> sort.
>
>
> On Wed, Aug 31, 2011 at 4:07 PM, Dave wrote:
>
>> @Bharatkumar: You've tacitly assumed that the data values are in the
>> range 0
@ dave- commplexity of radix sort is >= O(n log n). so better use heap sort.
On Wed, Aug 31, 2011 at 4:07 PM, Dave wrote:
> @Bharatkumar: You've tacitly assumed that the data values are in the
> range 0 to n-1. That's not given in the problem statement.
>
> Dave
>
> On Aug 31, 1:16 am, bharatkum
@Bharatkumar: You've tacitly assumed that the data values are in the
range 0 to n-1. That's not given in the problem statement.
Dave
On Aug 31, 1:16 am, bharatkumar bagana
wrote:
> bitset duplicates;// n- bit space..
> for(int i=0;i {
> if(duplicates[array[i]] ==1)
> print duplica
bitsetduplicates;// n- bit space..
for(int i=0;i wrote:
> Replying to myself... A radix sort takes O(n) extra space.
>
> Dave
>
> On Aug 30, 1:49 pm, Dave wrote:
> > @Kamakshii: With O(1) extra space, it can be done with O(n)
> > comparisons. Do a radix sort on the input (no comparisons), and
Replying to myself... A radix sort takes O(n) extra space.
Dave
On Aug 30, 1:49 pm, Dave wrote:
> @Kamakshii: With O(1) extra space, it can be done with O(n)
> comparisons. Do a radix sort on the input (no comparisons), and then
> check adjacent numbers for equality.
>
> Dave
>
> On Aug 30, 1:34
@Kamakshii: If you are willing to use O(n) extra space, you can use a
hash table. But with constant space, all the methods I can think of
are equivalent to sorting. Perhaps others can join in with constant-
space methods that don't involve sorting.
Dave
On Aug 30, 1:53 pm, Kamakshii Aggarwal wro
@dave:is there any other method than sorting?
On Wed, Aug 31, 2011 at 12:19 AM, Dave wrote:
> @Kamakshii: With O(1) extra space, it can be done with O(n)
> comparisons. Do a radix sort on the input (no comparisons), and then
> check adjacent numbers for equality.
>
> Dave
>
> On Aug 30, 1:34 pm,
@Kamakshii: With O(1) extra space, it can be done with O(n)
comparisons. Do a radix sort on the input (no comparisons), and then
check adjacent numbers for equality.
Dave
On Aug 30, 1:34 pm, Kamakshii Aggarwal wrote:
> develop an algorithm to find duplicates in a list of numbers without using a
14 matches
Mail list logo
