数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定一个已排序的包含 0 和 1 的数组，在 C++ 中查找数组的转换点。
给定一个仅包含 0 和 1 的已排序数字数组，找到转换点。转换点是指数组中第一个出现“1”的索引。例如：
输入 1 −
N = 6
arr[ ] = {0,0,0,0,1,1}输出 −
4
解释 − 在给定的包含 0 和 1 的数组中，我们可以看到索引“4”处的元素为“1”。
输入 2 −
N = 5
arr[ ] = {0,0,1,1,1}输出 −
2
解释 − 在给定的包含 0 和 1 的数组中，我们可以看到索引“2”处的元素为“1”。因此，我们将返回 2。
解决此问题的方法
在给定的整数数组中，我们必须找到第一个 1 的索引。为了解决这个问题，我们可以使用二分查找法来找到第一个“1”的索引。
输入 N 个二进制数的数组
现在，一个函数 `transitionPoint(int *arr, int n)` 以数组及其大小作为输入，并返回数组中第一个出现的“1”的索引。
取两个指针 `low` 和 `high`，分别初始化为“0”和“n-1”。
现在我们将找到数组的中点，并检查它是否为“1”。
如果数组的中点是“1”，那么我们将返回它的索引，否则我们将继续检查。
递增 `low` 指针并再次检查“1”。
重复这些步骤，直到我们找到“1”。
示例
#include <bits/stdc++.h>
using namespace std;
int transitionPoint(int *arr, int n){
int low=0;
int high= n-1;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid]==0)
low= mid+1;
else if(arr[mid]==1){
if(mid==0 || (mid>0 && arr[mid-1]==0))
return mid;
high= mid-1;
}
}
return -1;
}
int main(){
int n= 6;
int arr[n]= {0,0,0,1,1,1};
int ans= transitionPoint(arr,n);
if(ans>=0){
cout<<"Transition Point is:"<<ans<<endl;
}
else{
cout<<"Not Found"<<endl;
}
return 0;
}输出
运行上述代码将生成以下输出：
Transition Point is: 3
给定数组 {0,0,0,1,1,1} 在索引“3”处包含元素“1”，因此我们得到输出“3”。
更新于：2021年2月5日
572 次浏览
广告