2
Ist diese Algorithmus Arbeit als Lösung für 3sum in O(N log(N)), wo das Problem von Wikipedia alsLöst dies 3SUM in O (N log (N)) Zeit?
In Komplexitätstheorie definiert ist, fordert das 3sum Problem, wenn ein bestimmte Satz von n reellen Zahlen enthält drei Elemente, die Summe zu Null.
//Given an array of integers called list
//return true if 3 integers in list sum to 0, false otherwise
//quicksort the provided list
quickSort(list)
//add all elements of the list to a hashmap where the key is a number and the value is the number of times it occurs
hs = new hashMap<Integer, Integer>()
for(Integer i:list)
if(hs.get(i)==null)
hs.add(i, 1)
else
hs.add(i, hs.get(i)+1)
//create a pair of pointers pointing to the left of right of the center of array
startIndex=0
while (list[startIndex]<0 and startIndex<list.length-1)
startIndex++
left=startIndex
right=startIndex+1
//run this loop while pointers are in boundaries of array
while(! (left<0 or right>=list.length)
{
//see if a 3rd number that can be added to the numbers at left
//and right to make 0 can be found
sum=list[left] + list[right]
negsum= -(sum)
//if it's found enter these if statements
if(hs.get(negsum)!=null)
{
//check for the possibility that the 3rd number is one of the 1st 2, if not return true
if(negsum==list[left] or negsum== list[right])
{
//if the 3rd number is one of the 1st 2 make sure that a duplicate of it exists, or if all 3 are 0, that 3 zeros exist
//if we have enough duplicates, return true
if(list[left]==list[right])
if(list.hasMoreThanTwo(negsum))
return true
else if(list.hasMoreThanOne(negsum))
return true
}
else
return true
}
//if a trio cannot be formed with the numbers at left and right, adjust the pointers so that we will get closer to 0 and try again.
if (sum<0)
right++
else
left--
}
//if pointers go out of bounds 3 numbers that sum to 0 don't exist
return false
Ihr Algorithmus geht nicht über alle Optionen ... – alfasin