The question is to find the common elements in two arrays .The code which i wrote have the complexity of order n square.
How it can be done in linear timeCode:void main () { int i,j; int a[]={1,2,3,4}; int b[]={4,5,7,1}; for (i=0;i<4;i++) { for (j=0;j<4;j++) { if (a[i]==b[j]) { printf("%d",a[i]); } } } }
The obvious answer to me is it can be done if the arrays are sorted.Originally Posted by malwaregeek
Tim S.
"...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson
Yes in that case it could be definitely done in linear time. But even in case of unsorted arrays, it could be done ,one of my friend told me to use hashmap, but I have no idea how to implement though I know it theoretically.
With a hash map you would get O(n log n) time with O(n) additional memory. Pretty good, but not as O(n) time.
You can achieve O(n) time if the range of values is reasonably small: You set up an array of bits ---one for each possible value--- set to zero. Then mark with ones the bits of the values present in one array. Then traverse the other array, checking if its values were marked...
Oops. Sorry, I was thinking in a traditional [tree] map... With a hash map you can also get O(n) time, but only if you make the hash table reasonably big (proportional to the number of different values) and you avoid storing duplicates separately.
I was going to say. In practice the memory and computational overhead of a hash table is too high, and the way to do it is to sort both arrays. But a hash is an O(N) way of retrieving a database entry by content.
I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
Visit my website for lots of associated C programming resources.
https://github.com/MalcolmMcLean
I once began writing a modified IntroSelect sort of algorithm that operates on both arrays at once to see if their contents are the same but would allow for early outs that could mean it typically beats the hashing option in practice. Of course it requires that the array ordering need not necessarily be maintained. I never quite got it working properly in all cases and I cant remember where the code went.
I'd probably just sort both and compare. Radix Sort can be used to turn it into linear time, but if I was that intent on having it linear time then I'd probably just use a hash table.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
