有n个盒子,编号为1-n,共有a个小球,每个盒子最多可以放一个小球,现将小球放入连续编号的盒子中,用长度为n的数组arra表示n个盒子,1表示该盒子已经被检查过,0表示该盒子未被检查过,用数组arrb表示,
时间: 2024-05-19 10:13:34 浏览: 94
组合数学小球盒子问题
arrb[i]表示第i个盒子是否放有小球,放有为1,没放为0。现在要找出最左边和最右边的放有小球的盒子的编号。
一种解法是从左往右遍历arrb数组,找到第一个放有小球的盒子的编号,记为left。然后从右往左遍历arrb数组,找到第一个放有小球的盒子的编号,记为right。最后返回left和right即可。
时间复杂度为O(n)。
代码示例:
int left = -1, right = -1;
for(int i = 0; i < n; i++){
if(arrb[i] == 1){
left = i+1;
break;
}
}
for(int i = n-1; i >= 0; i--){
if(arrb[i] == 1){
right = i+1;
break;
}
}
return {left, right};
阅读全文