mine260309
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
A second thought is, we can have a struct with original value, square value and its original index, sort the struct with sqaure value, and do the search for the pythagorean triplets. This is O(N*logN)
Then we have both the original value (even it's negtive) and index.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Note when sorting the original list, you may lose the index information, so probably we should generate a index map that map the index from sorted array to the origina array's index. This algorithm may be O(n^2).
- mine260309 January 20, 2014Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
This solution works for a sorted array.
Based on this algorithm I have completed the code and it does work fine.
And note I use below struct as array items so that original value/index are recorded. Sort uses squareValue as key.
Sorting costs O(N*logN), iteration costs O(N^2).
- mine260309 January 21, 2014