剣指offer:面接問題3:配列で繰り返される数字

1.配列の紹介
まず配列について基本的に紹介し,配列の特徴は連続記憶である.C++では,一般に2種類の配列がある:1つは静的配列であり,その大きさを事前に知っていた.1つは動的配列,すなわちvectorであり,事前に大きさを規定しなくてもよい.
2.テーマ紹介
このタイプのテーマには、配列が秩序化されているかどうか、重複要素の個数など、多くのタイプがあります.
2.1配列内の重複要素の特定
長さnの配列のすべての数字は0からn-1の範囲内にある.配列のいくつかの数字は重複していますが、いくつかの数字が重複していることは分かりません.数字ごとに何回繰り返されるか分からない.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}が入力されると、対応する出力は、最初に繰り返される数字2である.
題意によれば,配列要素の範囲が決定され,最後の要求は任意の要素を出力することであることが分かる.
2.1.1並べ替え、次に巡回
配列が無秩序であることが知られており(秩序が無秩序であるとは言わない)、配列を先にソートすることができ、例えば{2,3,1,0,2,5,3}{2,3,1,0,5,3}{2,3,1,1,0,2,5,3}をソートした後、{0,1,2,2,3,3,5}{0,1,2,2,3,3,5}{0,1,2,2,3,3,5}を得ることができ、これにより、隣接する要素が等しいかどうかを判断することで、繰り返し要素を得ることができる.この時間的複雑度はO(nl o g n)O(nlogn)O(nlogn),空間的複雑度はO(1)O(1)O(1)であった.ソートは配列上で行われるからです.コードは次のとおりです.

bool duplicate1(int numbers[], int length, int* duplication) {
        sort(numbers,numbers+length);
        bool flag=false;
        for(int i=0;i<length-1;i++)
        {
            if(numbers[i]==numbers[i+1])
            {
                *duplication= numbers[i];
                flag=true;
                break;
            }
        }
        return flag;
}

2.1.2ハッシュ・テーブルの使用
配列の各要素は決定された範囲にあり、正数であるからです.配列をハッシュテーブルとして直接使用することができます.そこで、nの長さの配列を追加し、入力配列の要素を下付き文字として使用します.n u m={2,3,1,0,2,5,3}num={2,3,1,0,2,5,3}num={2,2,3,1,3,1,1,0,2,5,3}を例として,0,0,0,0,0,0,0,0,0,0,0,0,0,0}{0,0,0,0,0,0,0,0,0,}{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,}{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 7},すなわち、h a s h[i]=i hash[i]=i hash[i]=i hash[i]=i;だからh a s h[n u m[i]!=n u m [ i ] hash[num[i]]!=num[i] hash[num[i]]!=num[i]では,対応する要素をハッシュテーブルに入れる.例えば、n u m[0]=2 num[0]=2 num[0]=2;ha s h[2]hash[2]hash[2]はこのとき0であるため、ha s h[2]=2 hash[2]=2とする.n u m[4]num[4]num[4]num[4]を遍歴すると、h a s h[2]hash[2]hash[2]が2に等しいことがわかり、説明前に2に遭遇したことがあるので、2は重複要素である.空間複雑度はO(n)O(n)O(n)であり、時間複雑度はO(n)O(n)O(n)である.

bool duplicate2(int numbers[], int length, int* duplication) {
        bool flag=false;
        //array initialize
        int hash_t[length];
        for(int i=0;i<length;i++)
        {
            hash_t[i]=0;
        }
        for(int i=0;i<length;i++)
        {
            if(hash_t[numbers[i]]!=0)
            {
                flag=true;
                *duplication=numbers[i];
                 break;
            }
            else
                hash_t[numbers[i]]=numbers[i];
        }
        return flag;
}

2.1.3手動で配列を並べ替える
ハッシュテーブルを使用すると、空間の複雑さが高すぎます.ソートを使用すると、時間の複雑さが高すぎます.手動で入力配列をハッシュテーブルに並べ替える方法、すなわち各配列要素をその要素を下付きの位置に置く方法を採用しているからである.

{2,3,1,0,2,5,3}{2,3,1,0,2,3}{2,3,1,0,2,5,3}0番目の位置に対してnum[0]!=0、私たちは0がどこにあるか分かりませんが、num[0]=2この2がどこに置くべきか知っています.まず2番目の位置の値を調べてみると、2番目の位置の値は1で、2ではないことがわかります.そのため、0番目の位置の要素と2番目の位置の要素を交換します.すなわち、{1,3,2,0,2,2,5,5,{1,3,2,0,2,5,3}{1,3,2,5,3,3}

です.

交換後も、0番目の位置の要素は依然として要求に合致しないため、0番目の位置と1番目の位置の要素、すなわち{3,1,2,0,2,5,3}{3,1,2,2,5,3}{3,1,2,2,5,3}{3,1,2,2,5,3}

を交換する.

は依然として要求に合致せず、{0,1,2,3,2,5,3}{0,1,2,3,2,2,2,3,5}{0,1,2,3,2,2,2,5,3}

の操作を行う.

操作が完了すると、0~3番目の位置が要求に合致していることが判明したため、4番目の位置要素について操作を行い、4番目の位置要素は2であり、この位置の要素はすでに2であることが判明した.つまり、このとき交換する必要がなく、余分な2が現れたことを示している.順番に類推すると、すべての余分な要素を見つけることができます.

時間複雑度はO(n)O(n)O(n)、空間複雑度O(1)O(1)である.

bool duplicate3(int numbers[], int length, int* duplication) {

    bool flag=false;
    for(int i=0;i<length;i++)
    {
        while(numbers[i]!=i)
        {
            if(numbers[numbers[i]]==numbers[i])//satisfied hash condition
            {
                flag=true;
                *duplication=numbers[i];
                return flag;
            }
            //exchange
            int temp=numbers[i];
            numbers[i]=numbers[temp];
            numbers[temp]=temp;
        }

    }
    return flag;

}

3つ目の方法は最も効率的ですが、配列自体を修正しました.もしテーマが配列を修正しないことを要求したら?
2.2配列を変更せずに重複数を見つける(Leetcode.287重複数を探す)
n+1個の整数を含む配列numsが与えられ、その数はいずれも1〜nの間(1およびnを含む)であり、少なくとも1個の繰り返し整数が存在することが分かる.繰り返しの整数が1つしかないと仮定し、この繰り返しの数を見つけます.

   1:

  : [1,3,4,2,2]
  : 2
   2:

  : [3,1,3,4,2]
  : 3
  ：

       （        ）。
        O(1)    。
        O(n2) 。
            ，            。

2.2.1 hashテーブルの使用
配列要素の範囲が与えられているため、hashテーブルに配列を直接使用することができます.上記と同様に,O(n)O(n)O(n)の空間オーバーヘッドがある.

int findDuplicate(vector<int>& nums) {
        int n=nums.size();
        int result;
        vector<int>hash_n(n,0);
        for(int i=0;i<n;i++)
        {
            if(hash_n[nums[i]]!=0)
            {
                result=nums[i];
                break;
            }
            else
            {
                hash_n[nums[i]]=nums[i];
            }
        }
        return result;
    }

2.2.2二分検索の使用
配列を変更することはできないので、重複要素を検索する必要があります.重複する要素が1つしかないので、その重複する要素を見つけることが目標です.
すべての要素が1-nの間にあるので、n=5のような前後の2つの区間を区別することができ、私たちは2部1-2,3-5に分け、私たちはすべての要素のこの2つの区間の個数を統計し、[1,3,4,4,2][1,3,4,2][1,4,2]の間に3つあるが、区間長は2であり、その繰り返し要素が[1,2]の間にあることを説明する.次に、長さが1、すなわち統計1、2の回数であるため、繰り返し要素が2であることを再確認する.時間的複雑度はO(nl o g n)O(nlogn)O(nlogn),空間的複雑度はO(1)O(1)O(1)であった.

public:
    int CountNumber(vector<int>& nums,int start,int end_)
    {
    int n=nums.size();
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(nums[i]>=start&&nums[i]<=end_)
            ++ans;
    }
    return ans;
    }
    int findDuplicate(vector<int>& nums) {
        int length=nums.size();
        int start=1;
        int end_=length;
        while(start<=end_)
        {
            int mid=(start+end_)/2;
            int count_s_m=CountNumber(nums,start,mid);
            if(end_==start&&count_s_m>1)
                return start;
            if(count_s_m>mid-start+1)
                end_=mid;
            else
                start=mid+1;

        }
        return -1;
    }