给定一个大小为 t 的整数数组,需要找到中心索引。中心索引 x 是整数(0 到 x-1)之和等于总和(x+1 到 t-1)的索引。
我能想到的最好的算法是 O(n)。
我将有一个临时数组,其中包含之前所有整数的总和(不包括索引 x 处的整数):因此在索引 1 处它将是 1,在索引 2 处它将是 2 和 1 的总和,依此类推。
另一个 int 是所有 int 的总和。
我将循环遍历该数组两次,第一次创建临时数组,第二次查找两个部分是否相等。
是否有更好的 O(logn) 算法?
最佳答案
由于您必须计算数组的一半的总和,因此无法在 O(n)
内解决此问题。因为您必须至少检查每个元素一次(以计算总和)。仅当我们可以根据某些条件跳过检查数组的某些元素(此处不可能)时,任何算法都可以是 logn
。
关于arrays - 算法 - 找到中心索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12976612/