howie jao

Greenhorn

Posts: 14

posted 7 years ago

requirement: return sorted, no dup integer array. return size 0 array if no common found.

I have implemented in the following way:

1. create a third array to store common int . set size to max(array a, array b)

2. sort both array by quicksort

3. user for loop to find common value and store to third loop

4. fix integer 0 problem. when int array is initialize it put 0 . So I need to fix this

5. eliminate dup by run a for loop

This is definitely not the best way in term of time complexity. Can anyone provide better solution ?

I have implemented in the following way:

1. create a third array to store common int . set size to max(array a, array b)

2. sort both array by quicksort

3. user for loop to find common value and store to third loop

4. fix integer 0 problem. when int array is initialize it put 0 . So I need to fix this

5. eliminate dup by run a for loop

This is definitely not the best way in term of time complexity. Can anyone provide better solution ?

Embla Tingeling

Ranch Hand

Posts: 237

posted 7 years ago

What you want is the sorted intersection set between two sets.

I don't know if it's better but you can make use of the standard Java collections, like

I choose a TreeSet for set "a" because you want the output sorted. The "b" set is a HashSet for speed. Doubles are automatically removed when entered into a Set.

There's still a little work to do. The sets must be loaded from the int arrays and afterwards the "a" set must be dumped into an int array.

Well, it's probably faster to use two HashSets and then sort the result int array at the end. Then the algorithm will be linear all the way up to the sort. And hopefully there aren't that many elements left to sort so it will be fast although sorting isn't a linear operation.

howie jao wrote:Can anyone provide better solution ?

What you want is the sorted intersection set between two sets.

I don't know if it's better but you can make use of the standard Java collections, like

I choose a TreeSet for set "a" because you want the output sorted. The "b" set is a HashSet for speed. Doubles are automatically removed when entered into a Set.

There's still a little work to do. The sets must be loaded from the int arrays and afterwards the "a" set must be dumped into an int array.

Well, it's probably faster to use two HashSets and then sort the result int array at the end. Then the algorithm will be linear all the way up to the sort. And hopefully there aren't that many elements left to sort so it will be fast although sorting isn't a linear operation.

Embla Tingeling

Ranch Hand

Posts: 237

Campbell Ritchie

Sheriff

Posts: 55351

157

Embla Tingeling

Ranch Hand

Posts: 237

posted 7 years ago

That's why I said: IT'S LINEAR BUT REQUIRES THE INPUT ARRAYS TO BE SORTED.

The input requirement is two sorted arrays. Then the algorithm calculates the sorted intersection set in linear time.

Campbell Ritchie wrote:Are you sure it's linear complexity? Arrays.sort is merge sort, and that runs in O(nlogn) time.

That's why I said: IT'S LINEAR BUT REQUIRES THE INPUT ARRAYS TO BE SORTED.

The input requirement is two sorted arrays. Then the algorithm calculates the sorted intersection set in linear time.

posted 7 years ago

Embla, could you please use other means of emphasizing pieces of text? Quoted, bold or italic are much nicer to read than caps.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Embla Tingeling

Ranch Hand

Posts: 237

posted 7 years ago

Compare with the complexity of a binary search for example. It's generally considered O(lnN) but that's only because the dataset is specified to be initially sorted. If the sorting was considered part of the algorithm then also a binary search would be O(N * lnN).

That's why I emphasized in my post that the input arrays were to be considered intially sorted. I wrote

This means that the algorithm is linear or O(N) if the input arrays are sorted. Otherwise it won't even work, just like a binary search won't work if the dataset isn't sorted.

I hope this clarifies your doubts. If you have further questions please feel free to ask. I sinecerely applogize for any inconvenience you may have suffered due to my hard to understand sentence above.

Campbell Ritchie wrote:Agreed on that point.

Compare with the complexity of a binary search for example. It's generally considered O(lnN) but that's only because the dataset is specified to be initially sorted. If the sorting was considered part of the algorithm then also a binary search would be O(N * lnN).

That's why I emphasized in my post that the input arrays were to be considered intially sorted. I wrote

**It's linear but requires the input arrays to be sorted.**

This means that the algorithm is linear or O(N) if the input arrays are sorted. Otherwise it won't even work, just like a binary search won't work if the dataset isn't sorted.

I hope this clarifies your doubts. If you have further questions please feel free to ask. I sinecerely applogize for any inconvenience you may have suffered due to my hard to understand sentence above.