-
May 26th, 2010, 04:02 PM
#1
Would this Greedy algorithm work??
Hey
Got an exam on Friday for algorithms, it isnt my strong suit to be honest. Anyways one past paper question asks to design a greedy algorithm:
Have two arrays, Array Left and Array Right.
Design an algorithm such that left(i)+right(j)=0
EG: Left= 3 7 -2 2
Right=5 -3 -8 -8
Answer=i=1 and j=2
Brute force results in worst case quadratic complexity and is an inefficent solution.
My Solution:
Put the two arrays together, eg: 2 7 -2 2 5 -3 -8 -8
Sort them, using mergesort or something. eg -8 -8 -3 -2 2 3 5 7
Then have two pointers L and R.
L=1 //starts at begining of array
R=n // Starts at end of array
IF L+R < 0 //undershot target value 0
then
L=L+1
else IF L+R >0 //overshot target value 0
then
R=R-1
IF L+R=0 // solution found
then
return true
IF L>R //pointers cross so no solution
then
return false
This seems ok to me, what do you think?? Would result in worst case O(n.log n) due to the merge sort.
-
May 27th, 2010, 05:09 AM
#2
Re: Would this Greedy algorithm work??
Anyone? Just a quick Yes or No would help me out.
-
May 27th, 2010, 04:09 PM
#3
Re: Would this Greedy algorithm work??
Originally Posted by smithywill
Anyone? Just a quick Yes or No would help me out.
I don't think you have a working algorithm.
Is the problem that you want to know if a number in one array is present with the opposite sign in the other array? That would make their sum zero, right.
I don't quite see what merging and sorting the arrays will buy you. By doing that you no longer know which original array each number belongs to. A pair of numbers that sums to zero can as well come from the same array.
I suggest you just enter all numbers of one array into a hash set. Then you walk through the other array and check whether you have a match with opposite sign in the set. It's an O(N) algorithm.
Last edited by nuzzle; May 28th, 2010 at 01:00 AM.
-
November 27th, 2010, 04:21 AM
#4
Re: Would this Greedy algorithm work??
No it wont work.
Consider
Left = 3 -3
Right = 0 0
Merged and sorted = -3 0 0 3
L = 1
R = n
IF L+R=0 // solution found
then
return true
Though its obvious thats not true.
You should sort both left and right separately.
sort(left)
sort(right)
R = n;
L = 1;
if L + R < 0
L = L+1;
if L + R >0
R = R - 1;
if L + R = 0
return true;
if(L>n or R<0)
return false.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|