資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告