Frage TwoSum-Algorithmus: Wie kann dies verbessert werden?


Ich hatte das Gefühl, einen Algorithmus zu machen und dieses Problem gefunden zu haben Leetcode

Bei einem Array von Ganzzahlen finden Sie zwei Zahlen, die sich zu einer bestimmten Zielnummer addieren.

Die Funktion twoSum sollte Indizes der zwei Zahlen zurückgeben, so dass sie sich zum Ziel addieren, wobei index1 kleiner als index2 sein muss. Bitte beachten Sie, dass Ihre zurückgegebenen Antworten (sowohl index1 als auch index2) nicht nullbasiert sind.

Sie können davon ausgehen, dass jede Eingabe genau eine Lösung hätte.

Eingabe: Zahlen = {2, 7, 11, 15}, Ziel = 9

Ausgabe: Index1 = 1, Index2 = 2

Meine Lösung ist O (n ^ 2). Ich wollte wissen, ob es dafür einen besseren Weg gibt? wie O (n) oder O (nlogn)

import java.util.Arrays;
public class ReturnIndex {
    public int[] twoSum(int[] numbers, int target) {
        int tail = numbers.length-1;
        int[] n = new int[2];
        for (int i=0;i<tail;i++) {
            for(int j=i+1;j<tail;j++) {
                if(target ==(numbers[i]+numbers[j])) {
                    n[0] = i+1;
                    n[1] = j+1;
                }
            }
        }
        return n;
    }

    public static void main(String[] args) {
        int[] s = {150,24,79,50,88,345,3};
        int value = 200;
        ReturnIndex r = new ReturnIndex();
        int[] a = r.twoSum(s,value);
        System.out.println(Arrays.toString(a));
    }
}

6
2017-10-24 03:54


Ursprung


Antworten:


O(n log n) Zeit, O(1) Speicher (ohne die Liste zu zählen):

  1. Sortiere zuerst die Liste. Dies sollte dauern O(n log n) Zeit, wie die meisten Sortierfunktionen tun.

  2. Iteriere durch die Liste, die es dauern sollte O(n) Zeit in der äußeren Schleife. An dieser Stelle können Sie eine binäre Suche nach der am nächsten passenden Ganzzahl in einer sortierten Unterliste durchführen, die Sie durchführen sollten O(log n) Zeit. Diese Phase sollte beendet werden O(n log n) gesamt.

Bearbeiten: Schau dir die Antwort von Max unten an. Es ist immer noch O (n log n) Zeit und O (1) Speicher, aber er vermeidet die binären Suchen, indem er einen Zeiger von jedem Ende der Liste führt.

O(n) Zeit, O(n) Erinnerung:

Erstellen Sie eine Hash-Tabelle, die haben sollte O(1) Einfügen und O(1) enthält. Dann, in einem O(n) äußere Schleife, für jede Zahl i, überprüfe ob total - i ist in der Hash-Tabelle. Wenn nicht, füge es hinzu; Wenn ja, dann hast du deine zwei Zahlen.

In jedem Fall benötigen Sie einen zusätzlichen Scan durch das Array, um die Indizes zu erhalten, aber das ist kein Problem - es dauert nur O(n) Zeit. Wenn Sie es vermeiden möchten, können Sie den ursprünglichen Index in der sortierten Liste oder der Hashtabelle nach Bedarf beibehalten, jedoch mit einem Speicherbedarf anstelle eines Zeitfußabdrucks.


7
2017-10-24 04:12



Sortiere das Array. Stelle zwei Zeiger auf den ersten und letzten Punkt (x und X). Führen Sie dies in einer Schleife aus:

if      (a[X]+a[x] >  N) then X-- 
else if (a[X]+a[x] <  N) then x++
else if (a[X]+a[x] == N) then found.

if (x > X) then no numbers exist.

O(nlogn) Zeit, O(1) Erinnerung


8
2017-10-24 04:12



Im Folgenden finden Sie eine Lösung, in der die beiden Zahlen gefunden werden können O(n log n) Zeit:

1- Sort the numbers in ascending (or descending) order             // O(n log n)

2- Compute diff = target - item for each item                      // O(n) 

3- For each calculated diff, look up the calculated value in the sorted items 
   using the Binary search algorithm                               // O(n log n) 

Eine vollständige, funktionierende Implementierung in Java:

import java.util.ArrayList;

public class NumbersFinder {

    class Item{
        private int value;
        private int index;

        public Item(int value, int index){
            this.value = value;
            this.index = index;
        }

        public int getValue(){
            return value;
        }

        public int getIndex(){
            return index;
        }
    }

    public ArrayList<Item> find(int[] values, int target){      
        ArrayList<Item> items = new ArrayList<Item>();
        for(int i = 0; i < values.length; i++)
            items.add(new Item(values[i], i));

        items = quicksort(items);
        ArrayList<Integer> diffs = computeDiffs(items, target);

        Item item1 = null;
        Item item2 = null;

        boolean found = false;

        for(int i = 0; i < diffs.get(i) && !found; i++){
            item1 = items.get(i);
            item2 = searchSortedItems(items, diffs.get(i), 0, items.size());
            found = item2 != null;
        }
        if(found){
            ArrayList<Item> result = new ArrayList<Item>();
            result.add(item1);
            result.add(item2);
            return result;
        }
        else
            return null;
    }

    // find "value" in the sorted array of "items" using Binary search in O(log n)
    private Item searchSortedItems(ArrayList<Item> items, Integer value, int lower, int upper) {
        if(lower > upper)
            return null;
        int middle = (lower + upper)/2;
        Item middleItem = items.get(middle);
        if(middleItem.getValue() == value)
            return middleItem;
        else if(middleItem.getValue() < value)
            return searchSortedItems(items, value, middle+1, upper);
        else
            return searchSortedItems(items, value, lower, middle-1);
    }

    // Simply calculates difference between the target value and each item in the array; O(n)
    private ArrayList<Integer> computeDiffs(ArrayList<Item> items, int target) {
        ArrayList<Integer> diffs = new ArrayList<Integer>();
        for(int i = 0; i < items.size(); i++)
            diffs.add(target - items.get(i).getValue());
        return diffs;
    }

    // Sorts items using QuickSort algorithm in O(n Log n)
    private ArrayList<Item> quicksort(ArrayList<Item> items) {
        if (items.size() <= 1)
            return items;
        int pivot = items.size() / 2;
        ArrayList<Item> lesser = new ArrayList<Item>();
        ArrayList<Item> greater = new ArrayList<Item>();
        int sameAsPivot = 0;
        for (Item item : items) {
            if (item.getValue() > items.get(pivot).getValue())
                greater.add(item);
            else if (item.getValue() < items.get(pivot).getValue())
                lesser.add(item);
            else
                sameAsPivot++;
        }
        lesser = quicksort(lesser);
        for (int i = 0; i < sameAsPivot; i++)
            lesser.add(items.get(pivot));
        greater = quicksort(greater);
        ArrayList<Item> sorted = new ArrayList<Item>();
        for (Item item : lesser)
            sorted.add(item);
        for (Item item: greater)
            sorted.add(item);
        return sorted;
    }


    public static void main(String[] args){
        int[] s = {150,24,79,50,88,345,3};
        int value = 200;

        NumbersFinder finder = new NumbersFinder();
        ArrayList<Item> numbers = finder.find(s, value);

        if(numbers != null){
            System.out.println("First Number Found = " + numbers.get(0).getValue() + " ; Index = " + + numbers.get(0).getIndex());
            System.out.println("Second Number Found = " + numbers.get(1).getValue() + " ; Index = " + + numbers.get(1).getIndex());
        }
        else{
            System.out.println("No such two numbers found in the array!");
        }
    }
}

Ausgabe:

First Number Found = 50 ; Index = 3
Second Number Found = 150 ; Index = 0

2
2017-10-24 04:17



Ich würde es so angehen:

  1. Ordnen Sie Ihr Array von kleineren zu niedrigeren Werten

  2. Überstreichen Sie Ihr Array so, wie Sie es haben, aber verlassen Sie die Schleife immer dann, wenn Sie es möchten

    Ziel <(Zahlen [i] + Zahlen [j])

  3. Sobald Sie den Wert Ihrer zwei Elemente haben, so dass n [0] + n [1] = Ziel, schauen Sie zurück zum ursprünglichen Array, um ihren Index zu finden.


0
2017-10-24 04:10



Eine Zeilenlösung in Python:

class Solution(object):
    """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
    """
    def twoSum(self, nums, target):            
        x = [[i, nums.index(target-j)] for i,j in enumerate(nums) if nums.count(target-j) > 0 and nums.index(target-j)!=i]

        return x.pop()

0
2017-09-13 11:48



Hier ist meine cpp-Lösung mit O (nlog (n)):

vector<int> two_sum(vector<int> &numbers, int target) {
    vector<int> result;
    vector<int> numbers_dup = vector<int>(numbers);

    sort(numbers_dup.begin(), numbers_dup.end());

    int left = 0, right = numbers_dup.size() - 1;
    while(left <= right) {
        int sum = numbers_dup[left] + numbers_dup[right];

        if(sum == target) {
            //find the idex of numbers_dup[left] and numbers_dup[right]
            for(int i = 0; i < numbers.size(); i++) {
                if(numbers[i] == numbers_dup[left] || numbers[i] == numbers_dup[right]) {
                    result.push_back(i);
                }
                if(result.size() == 2) {
                    return result;
                }
            }
        }
        else if(sum > target) {
            right--;
        }
        else {
            left++;
        }
    }
}

In meinem Blog finden Sie eine detaillierte Erklärung. https://algorithm.pingzhang.io/Array/two_sum_problem.html


0
2017-10-02 02:00



Hier ist die Antwort mit HashMap in Java mit zwei Durchläufen des Arrays. Angenommen, es gibt keine doppelten Elemente im Array, und es gibt genau eine Lösung.

import java.util.HashMap;

public class TwoSum {

    int[] index = new int[2];
    public int[] twoSum(int[] nums, int target)
    {
        int length = nums.length;
        //initialize return values assuming that pair for the given target
        //doesn't exist
        index[0]=-1;
        index[1]=-1;
        //sanity check
        if(length<1) return index;

        HashMap<Integer, Integer> numHash = new HashMap<>(length);
        //get the values from array into HashMap assuming that there aren't duplicate values
        for(int i=0; i<length;i++)
        {
            numHash.put(nums[i],i);
        }

        //check for the value in the array and the difference between target and it. Assume that only
        //one such pair exists
        for(int i=0;i<length;i++)
        {
            int val1 = nums[i];
            int val2=target-val1;
            //make sure that it doesn't return the index of the first number in the pait you are searching for
            if( numHash.containsKey(val2) && numHash.get(val2)!=i){
                index[0]=i;
                index[1] =numHash.get(target-nums[i]);
                break;
            }
        }
        return index;
    }
}

0
2017-08-07 04:02



 public static int[] twoSum(int[] nums, int target) {
        int []resultarray=new int[2];
        for (int i=0;i<nums.length-1;i++){
            for(int k=1;k<nums.length;k++)
            {
                 if(target==nums[i]+nums[k])
                 {
                     resultarray[0]=nums[i];
                     resultarray[1]=nums[k];
                 }
            }
        }
 return resultarray;
    }

0
2017-08-14 10:48



Dies ist meine Python-Lösung

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        copy_dict = {}
        for pos in range(0, len(nums)):
            if nums[pos] not in copy_dict.keys():
                copy_dict[nums[pos]] = [pos]
            else:
                copy_dict[nums[pos]].append(pos)

        def get_sum_indexes(sorted_array, target):
            right_pointer = len(sorted_array) - 1
            left_pointer = 0
            while left_pointer < len(sorted_array) or right_pointer > 0:
                if sorted_array[right_pointer] + sorted_array[left_pointer] == target:
                    return [sorted_array[left_pointer], sorted_array[right_pointer]]
                elif sorted_array[right_pointer] + sorted_array[left_pointer] > target:
                    right_pointer -= 1
                elif sorted_array[right_pointer] + sorted_array[left_pointer] < target:
                    left_pointer += 1
            return None
        sum_numbers = get_sum_indexes(sorted(nums), target)
        if len(copy_dict[sum_numbers[0]]) == 1:
            answer_1 = copy_dict[sum_numbers[0]][0]
        else:
            answer_1 = copy_dict[sum_numbers[0]][0]

        if len(copy_dict[sum_numbers[1]]) == 1:
            answer_2 = copy_dict[sum_numbers[1]][0]
        else:
            answer_2 = copy_dict[sum_numbers[1]][1]
        return sorted([answer_1, answer_2])

print(Solution().twoSum(nums=[-1, -2, -3, -4, -5], target=-8))
print(Solution().twoSum(nums=[-3, -3], target=-6))

0
2017-12-19 20:51