数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找排序后的 0 和 1 数组中第一个 1 的索引
在这个问题中，我们得到一个由布尔值（只有 0 和 1）组成的排序数组 bin[]。我们的任务是查找排序后的 0 和 1 数组中第一个 1 的索引。
让我们来看一个例子来理解这个问题：
Input : bin[] = {0, 0, 0, 1, 1}
Output : 3解释 −
First 1 of the binary array is encountered at index 3.
解决方案方法
为了解决这个问题，我们基本上需要找到数组中第一个 1 的索引。为此，我们可以使用搜索技术。
一种方法可以使用线性搜索，我们将从索引 0 遍历到数组的末尾。并返回数组中第一个 1 的索引，否则打印 -1。
示例
程序演示了我们解决方案的工作原理
#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
for (int i = 0; i < n; i++)
if (bin[i] == 1)
return i;
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
return 0;
}输出
The index of 1st occurrence of 1 in array is 3
另一种可以使用的搜索技术是二分查找，因为数组已排序。
示例
程序演示了我们解决方案的工作原理
#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
int low = 0;
int high = (n - 1);
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
return mid;
else if (bin[mid] == 1)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
return 0;
}输出
The index of 1st occurrence of 1 in array is 3
更新于：2022-01-28
447 次浏览
广告