1991. 找到数组的中间位置-贪心算法+前缀和
2023-09-14 09:06:52 时间
1991. 找到数组的中间位置
给你一个下标从 0 开始的整数数组 nums ,请你找到 最左边 的中间位置 middleIndex (也就是所有可能中间位置下标最小的一个)。
中间位置 middleIndex 是满足 nums[0] + nums[1] + … + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + … + nums[nums.length-1] 的数组下标。
如果 middleIndex == 0 ,左边部分的和定义为 0 。类似的,如果 middleIndex == nums.length - 1 ,右边部分的和定义为 0 。
请你返回满足上述条件 最左边 的 middleIndex ,如果不存在这样的中间位置,请你返回 -1 。
示例 1:
输入:nums = [2,3,-1,8,4]
输出:3
解释:
下标 3 之前的数字和为:2 + 3 + -1 = 4
下标 3 之后的数字和为:4 = 4
示例 2:
输入:nums = [1,-1,4]
输出:2
解释:
下标 2 之前的数字和为:1 + -1 = 0
下标 2 之后的数字和为:0
示例 3:
输入:nums = [2,5]
输出:-1
解释:
不存在符合要求的 middleIndex 。
这题使用贪心算法和前缀和去做,解题代码如下:
int findMiddleIndex(int* nums, int numsSize){
int sum=0;
int i;
if(numsSize==1){
return 0;
}
for(i=0;i<numsSize;i++){
sum=nums[i]+sum;
}
int presum=0;
for(i=0;i<numsSize;i++){
presum=nums[i]+presum;
if(sum-presum==presum-nums[i]){
return i;
}
}
return -1;
}
相关文章
- 一个计算数字数组概览的算法2
- Java实现完美洗牌算法
- Java实现 蓝桥杯VIP 算法提高 递归倒置字符数组
- Java实现 蓝桥杯VIP 算法提高 递归倒置字符数组
- Java实现 蓝桥杯 算法训练 动态数组使用
- Java实现 蓝桥杯 算法训练 删除数组零元素
- Java实现 蓝桥杯 算法训练 寻找数组中最大值
- Java实现 蓝桥杯 算法训练 最大最小公倍数
- Java实现 蓝桥杯 算法训练 区间k大数
- Java实现算法提高十进制数转八进制数
- 【学习总结】java数据结构和算法-第三章-稀疏数组和队列
- 基础算法练习200题12、统计奇偶数
- 动手实操丨基于随机森林算法进行硬盘故障预测
- 智能优化算法:社交网络搜索算法-附代码
- (转)十大滤波算法程序大全Arduino
- 350. 两个数组的交集 II-暴力算法+原地修改
- 1582. 二进制矩阵中的特殊位置-时间空间双重优化算法
- 【算法题】输入一维数组array和n,找出和值为n的任意两个元素
- 重拾算法(2)——线索二叉树
- Redis源代码分析(23)--- CRC循环冗余算法RAND随机数的算法
- Python ---- 算法入门(2)分治算法解决【找数组的最大值和最小值】问题