首页 文章

使用索引任一侧的值增加来查找数组中的最大值

提问于
浏览 次
4

我试图解决一个需要在数组中找到最大值的问题 . 数组不能被强力搜索，因为它非常大（超过100,000,000个元素）所以我试图创建二进制搜索的修改版本以找到最大值 .

该数组的特定属性是：

  • 数组是循环的

  • 从数组中的最小值索引开始，超过此索引的所有值将增加或保持不变，直到最大值的索引 . 从这里，值将保持不变或减少

  • 最小值的索引与最大值的索引相反

某些数组的示例是（所有等效数组）：

  • {1, 2, 3, 4, 5, 5, 4, 3, 2, 1}

  • {5, 4, 3, 2, 1, 1, 2, 3, 4, 5}

  • {3, 4, 5, 5, 4, 3, 2, 1, 1, 2}

有没有人有任何想法在大约O（logN）时间解决这个问题？

如何计算数组值：

unsigned long long calculateArrayValue(unsigned long long location, unsigned long long n, unsigned long long arrayLength, unsigned long long* arrayIndices, unsigned long long* locationMagnitude) {
    unsigned long long value = 0;
    unsigned long long halfArrayLength = arrayLength/ 2;
    unsigned long long difference;
    for (unsigned long long i = 0; i < n; i++) {
        if (arrayIndices[i] > location) {
            difference = arrayIndices[i] - location;
        } else {
            difference = location - houseLocations[i];
        }
        if (difference > halfArrayLength ) {
            difference = arrayLength - difference;
        }
        value += difference * locationMagnitude[i];
    }

    return value;
}
c++ arrays

1 回答

  • 4

    如果您允许n-1次相同的数字列表和1次更大的列表，例如

    5 5 5 5 5 5 5 6 5，

    然后我声称你通常不能在O（log n）时间内解决问题，因为问题相当于搜索1 in

    0 0 0 0 0 0 0 1 0

    因此，您有效地在未排序的列表中搜索特定条目，这需要O（n）时间 .

    当然，您可以加快特殊情况的算法，例如：通过将线性搜索与二分搜索相结合，允许您跳过严格减少列表的子序列 .

    The following solution is wrong, see comments.

    伪代码：

    int next (int i) {
   return i + 1 < length ? i + 1 : 0;
}

int prev (int i) {
   return i - 1 < 0 ? length : i - 1;
}

int lower = 0;
int upper = length - 1;
int tmp;

while (true) {
   tmp = (upper + lower) / 2;
   if ( (ary [prev(tmp)] <= ary [tmp]) && (ary [next(tmp)] <= ary [tmp]) ) break;

   if ( ary [prev(tmp)] <= ary [tmp] ) {
      lower = tmp;
   } else if ( ary [next(tmp)] <= ary [tmp] ) {
      upper = tmp;
   } else {
      /* we have found a minimum! */
      tmp = length - 1 - tmp;
      break;
   }
}

int maximum_index = tmp;
    回复于

相关问题