查找数列中数的位置

WingDust
  • 116

有一列数组

  • 全部为正整数或 0
  • 数组中可以有相同的数

求解
给定一个数在小于数组总和大于等于 0 之间的正整数,
求从数组 0 开始向后依次相加,根据相加的值给定的数进行比较,
相加值大于或等于给定数的差距最小时,返回当前相加的最后一位

如:
[0,1,90,30,67,30,2,4,5,610,34,0] 总和:873 长度:11

给定的数:30 返回数组索引 2
因为 (0 + 1 + 90) > 30 这个最小的大于值

给定的数:122 返回数组索引 4
因为 (0 + 1 + 90 + 30 +67) > 122 这个最小的大于值

给定的数:0 返回数组索引 0
因为 0 = 0 这个最小的等于值 (当为 0 时 只有索引 0 满足条件 所以可以直接返回 0)

想知道有没有时间复杂度与空间复杂度较优的JavaScript | TypeScript | Rust

回复
阅读 301
1 个回答

这道题不难啊,因为限定很多的,特别是给的数是[0,数组和]内的,而且所有数都是非负数,则直接累加比较加终止条件就好

let a=[0,1,90,30,67,30,2,4,5,610,34,0]
function getIdx(x,arr){
    let i=0;
    let sum=0;
    let len=arr.length;
    for(;i<len;i++){
        sum=sum+arr[i];
        if(sum>=x) break;
    }
    return i; // 这样是算法判断不了是否出错,其实稍微处理一下,如果x大于数组和,则返回-1也是可以的,比如 
    //return ( (sum>=x)?i:-1);
}
console.log( getIdx( 30,a) );
console.log( getIdx( 122,a) );
console.log( getIdx( 0,a) );
console.log( getIdx(873,a) );

因为这个方案复杂度已经是O(n)的啦,基本没有太多优化空间啊,毕竟就是数组求1次和也需要O(n)啊。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏