查找与存在于阵列中的大多数值

例排序位置矢量[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

查找与存在于阵列中的大多数值

回答

相关问题