(C++)剣指offer-拡張:配列を修正せずに重複する数字(配列)を見つける

配列を変更せずに重複する数を見つける

二分ルックアップアルゴリズムの概念(最適)1)を用いて1 nの数字を中間の数字mから2つの部分に分け,前半が1 m,後半がm+1~n 2)1~mの部分の数字対応配列の値がm個を超えると,この区間には重複する数字が含まれ,そうでなければ別の区間に重複する数字が含まれる.2つの区間が重複していても、ある区間を2点するだけで、問題はいずれかの重複する数字を見つけることを要求しているため3)重複する数字の区間を2点し続け、1つの重複する数字

が見つかるまで続ける.

二分ルックアップアルゴリズムテンプレートC++コードテンプレート:

int bsearch_1(int l, int r)
{
     
    while (l < r)
    {
     
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

詳細な問題解

Class Solution{
     
	public:
		int duplicateInArray(vector<int>& nums){
     
			int l = 1, r = nums.size() - 1; //opps
			while(l < r){
     
				int mid = l + r >> 1; // [l, mid]  [mid+1, r]
				int count = 0; //opps
				for(auto x : nums){
     
					count += x >= l && x <= mid; //opps
				}
				if(count > mid - l + 1) r = mid;
				else l = mid + 1; //opps
			}
			return r;
		}
}