查找與存在於陣列中的大多數值

例排序位置矢量[4，5，9，30，31，32，34，40，47] 間隔長度的陣列間隔= 6查找與存在於陣列中的大多數值

我想找到在長度爲6的任何給定的時間間隔在上述示例的值的最大數目，則間隔將是 [數組值 - 陣列值+間隔長度：此數組中的本#Values]

4 - 10：3（4,5,9）
5 - 11：2（5,9）
9 - 15：1（9）
30 - 36：4（30，31，32，34）
31 - 37：3
32 - 38：2
34 - 40： 2
40 - 46：1
47 - 53：0

答案應該是30-36，因爲它有這4任何人有關於如何找到這個任何好的想法值的最大數量最佳？

來源

2011-01-21 smitten

編程語言是否重要，或者是任何語言的算法（甚至是僞代碼）都很好？ – BoltClock 2011-01-21 02:03:17

我不明白你在O（n.k）時間下如何做到這一點，其中n是數組中項目的數量，k是'間隔長度'。

對於n中的每個元素，您需要檢查'間隔'直到接下來的k個元素。

我考慮過預處理數組以獲得間隔值的矩陣，但這需要與基本樸素算法相同的複雜度。

來源

2011-01-21 02:28:08

這是我能想到的最快的方式。另外，請注意：您定義的時間間隔爲6，但隨後表示，它包含的項目30至36（那7項），所以我基於這樣寫這個代碼：

int GetInterval(const vector<int> &sortedList, int intervalLength) 
{ 
    int lowest = sortedList[0]; 
    int highest = sortedList[sortedList.size()-1]; 
    vector<int> intervals(highest-lowest-intervalLength+1, 0); 
    int max = 0; 

    for(int i = 0; i < sortedList.size(); i++) 
    { 
    int base = sortedList[i] - lowest; 
    for(int j = -intervalLength; j <= intervalLength; j++) 
    { 
     int index = i + j + base; 
     if(index < 0 || index >= intervals.size()) continue; 
     if(++intervals[index] > intervals[max]) max = index; 
    } 
    } 

    return max + lowest; 
}

所以，我的天堂」實際上跑這個，但它應該工作。其大O是排序列表的長度乘以區間長度。如果你把整個區間長度作爲一個常量，那麼它就是O（n）。希望這對你有用。另外，我希望C++也適合你。

*注意它返回間隔中的最小數字。

來源

2011-01-21 02:57:36

這將反向掃描列表以消除一些回溯。

size_t find_interval(const std::vector& _positions, int _interval) 
{ 
    assert(_positions.size() >= 2); 

    size_t start_of_run = 0; 
    size_t end_of_run; 
    size_t idx; 
    size_t run_length = 0; 

    end_of_run = _positions.size() - 1; 
    idx = end_of_run - 1; 
    for(; idx >= 0; --idx) 
    { 
     if((_positions[end_of_run] - _positions[idx]) <= _interval) 
     { 
      // idx is still in the interval, see if it's the longest 
      // run so far 
      if((end_of_run - idx) > run_length) 
      { 
       start_of_run = idx; 
       run_length = end_of_run - idx; 
      } 
     } 
     else 
     { 
      // idx is out of the interval, so move end_of_run down to 
      // make a new valid interval 
      do 
      { 
       --end_of_run; 
      } while((_positions[end_of_run] - _positions[idx]) > _interval); 

      // we don't care about a run smaller than run_length, so move 
      // idx to the shortest interesting run 
      idx = end_of_run - run_length; 
     } 
    } 

    return start_of_run; 
}

的end_of_run變量可以用idx和end_of_run之間的二進制搜索更有效地進行更新，但它使算法難於理解。

來源

2011-01-21 04:23:17 Alex

查找與存在於陣列中的大多數值

回答

相關問題