Pseudocode/Java基本數組求和算法

我剛剛在介紹性CS課程的期末考試中遇到了這個問題。我認爲這很有趣，但我無法完全弄清楚。我試着在Eclipse上編碼一段時間，但沒有到任何地方。我很快就會參加Biochem考試，所以我真的應該爲此做些研究，但這是在煩擾我......我想我會尋求幫助。Pseudocode/Java基本數組求和算法

問題 - 爲以下內容編寫算法：給定一個輸入數組A，帶有2個索引 - 開始和結束 - 計算兩者之和。數組被排序並且所有元素都屬於集合{1,2,3}。該算法必須在O（log（n））中運行。所以給出一個數組{1，1，2，2，3，3,3，3}與指數1和5這將返回11

這是我到目前爲止有：

public static int findSum(int[] a, int start, int stop) { 

    int sum = 0; 

    int temp[] = new int[4]; 
    int mid = (start+stop)/2; 

    while (mid > start || mid < stop) { 

     if (a[mid+1]-a[mid] != 0) { 
      temp[mid+1] = mid+1; 
      temp[mid] = mid; 
      mid++; 
     } 
     else { 
      findSum(a, start, mid); 
      findSum(a, mid+1, stop); 
     } 
    } 
    for (int i = 4; i > 0; i--) { 
     if (temp[i] == 0) { 
      temp[i] = temp[i-1]; 
     } 
    } 
    for (int i = 1; i < 4; i++) { 
     sum += i*(temp[i]-temp[i-1]); 
    } 
    return sum; 
}

不知道我的邏輯是否正確，但我的想法是在數組中移動並查找索引，並以遞歸方式執行此操作，並將數組分成兩部分。通過這些指標，我可以確定數字出現的頻率，然後將這些數字乘以這些頻率並將其相加以計算總和。

很肯定我的算法中有許多缺陷...

來源

2014-12-11 rahc01

您確定此問題不是關於* search *算法嗎？即[二進制搜索]（http://en.wikipedia.org/wiki/Binary_search_algorithm）。當你添加數組範圍內的所有東西時，無論如何你都會有一個O（n）操作：你不可避免地必須計算範圍內的每個數字。由於數組已經排序，我已經更加確信這就是問題所在（爲了寫出二進制搜索算法）。 – Rogue 2014-12-11 00:42:24

你已經更新了你的問題，我現在看到你在問什麼，回答... – Rogue 2014-12-11 00:45:44

現在你已經更新了你的問題，包括數據將只在這1，2，或3：你可以簡單地僅僅遞歸請檢查您所在的範圍內的號碼：

public static int findSum(int[] a, int start, int stop) { 
    if (start < 0 || start >= a.length || stop < 0 || stop >= a.length) { //bounds check 
     return 0; 
    } 
    if (start == stop) { //return the number! 
     return a[start]; 
    } else if (a[start] == a[stop]) { //catch for some quick math, return amount of values * the value 
     return a[start] * (stop - start + 1); 
    } else { 
     int mid = start + ((stop - start) >>> 1); //This is the middle point between start and stop 
     return findSum(a, start, mid) + findSum(a, mid + 1, stop); 
    } 
}

來源

2014-12-11 00:55:03 Rogue

謝謝！當我有一些時間時，我會看看這個 – rahc01 2014-12-13 23:01:21

Pseudocode/Java基本數組求和算法

回答

相關問題