剣指offer(03):配列中に繰り返される数字(C++&Python実装)

1題目配列の中で重複する数字を探し出すと
1.1説明
長さnの配列のすべての数字は0からn-1の範囲内にある.配列の中にはいくつかの数字が重複していますが、いくつかの数字が重複しているのか、数字ごとに何回重複しているのか分かりません.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力すると、対応する出力は重複する数字2または3である.
1.2問題解
方法1
入力した配列を並べ替えます.並べ替えられた配列から重さ0の数字を探し出し、並べ替えられた配列を最初から最後までスキャンするだけです.時間複雑度O(nlogn).
方法2
ハッシュテーブルを用いて,配列の各配列を最初から最後まで順番にスキャンし,1つの数字をスキャンするたびにO(1)の時間でハッシュテーブルにこの数字が含まれているか否かを判断することができる.ない場合はハッシュ・テーブルを追加します.既に存在する場合は、重複する数値が表示されます.時間複雑度O(n)は,時間効率を向上させる代価として空間複雑度O(n)のハッシュテーブルである.
方法3
時間複雑度がO(n)、空間複雑度がO(1)の方法はありますか?
配列長がnであり、数値範囲が0~n−1であることに注意し、重複する数字がなければ、配列並べ替え後の数字iは、下のiと表記された位置に現れ、値と下の1つに対応する.繰り返すと、下付き文字の対応する位置に同じ数字が複数存在する場合があります.
この配列を並べ直して、各数字を最初から最後まで順番にスキャンしましょう.下のiと表記された数字をスキャンすると、まずこの数字(m)がiに等しいか否かを判断する.もしそうであれば、次の数値をスキャンします.そうでない場合は、下にmと表記された数字と比較し、等しい場合は繰り返しの数字(この数字は下にiとmと表記された位置に現れた)を見つけ、等しくない場合は両者の位置を交換する.数字mが下付きmに対応するようにする.次に、重複する数値が見つかるまでこのプロセスを繰り返します.
たとえば、{2,3,1,0,2,4}の配列があります.
—> {1,3,2,0,2,4}
—> {3,1,2,0,2,4}
->{0,1,2,3,2,4}重複数が見つかりました.
1.3コード
C++

/*
  :
    numbers:           
    length:           
    duplication: (  )            
   :
    true  -     ，            
    false -     ，            
*/
bool duplicate(int numbers[], int length, int* duplication)
{
    //       ，      0
    if (numbers == nullptr || length <= 0)
        return false;

    //           0~n-1
    for (int i = 0; i < length; i++)
    {
        if (numbers[i] < 0 || numbers[i] > length - 1)
            return false;
    }
    for (int i = 0; i < length; ++i)
    {
        while (numbers[i] != i)
        {
            //           ，   ture
            if (numbers[i] == numbers[numbers[i]])
            {
                *duplication = numbers[i];
                printf("%d", *duplication);
                return true;
            }
            //       numbers[i]   numbers[numbers[i]]
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return false;
}

Python

class Solution:
    def duplicate(self, numbers, duplication):
        if numbers == None or len(numbers) <=0:
            return False
        for i in numbers:
            if i > len(numbers) - 1 or i < 0:
                return False
        for i in range(len(numbers)):
            while numbers[i] != i:
                if numbers[i] == numbers[numbers[i]]:
                    duplication.append(numbers[i])              
                    print(duplication[0])
                    return True
                else:
                    index = numbers[i]
                    numbers[i], numbers[index] = numbers[index], numbers[i]
        return False

s = Solution()
array = [1, 2, 3, 3, 4, 4]
duplication = []
s.duplicate(array, duplication)

コードには二重ループがありますが、数字ごとに最大2回交換すれば自分の位置を見つけることができます.従って、時間的複雑度はO(n)であり、空間的複雑度はO(1)である.
2題目2配列を修正せずに重複する数字を探し出す
2.1説明
長さn+1の配列のすべての数字は1からnの範囲内にあるので、配列の少なくとも1つの数字は重複しています.配列のいずれかの重複する数字を見つけてくださいが、入力した配列は変更できません.例えば、長さ8の配列{2,3,5,4,3,2,6,7}を入力すると、対応する出力は重複する数字2または3である.
2.2問題解
方法1
入力配列を変更できないため、n+1の長さの補助配列を作成し、元の配列の数字を補助配列に1つずつコピーすることができます.元の配列の数字がmであれば、配列の下にmと表記された位置にコピーします.継続的に実行すると重複する数が見つかるが,これはO(n)の補助空間を必要とする.
方法2
次に,O(n)の補助空間の使用を避けた.重複する数字がないと仮定すると,その1~nの範囲内には最大でn個の数字しかないのに対し,タイトルにはn+1個の数字があるので,必ず重複する数字が存在する.だからある範囲の数字の個数はこの問題を解決するのに重要です.
原配列の数値範囲は1~nであり,中間サイズmで原配列を大きさ範囲で2つの部分に分け,前半の大きさ範囲は1~m,後半の範囲はm+1~nである.範囲1~mの数がm個を超えると、その中に必ず重複数が存在し、そうでなければ後半に重複数が存在する.重複する数字が見つかるまで、重複する数字を含む範囲を2つに分け続けます.
2.3コード
C++

//   :
//        numbers:           
//        length:           
//    :             
//            -     ，            ，         
//            -     ，            
int getDuplication(const int* numbers, int length)
{
    if (numbers == nullptr || length <= 0)
        return -1;

    //      n + 1,      1 ~ n
    int start = 1;
    int end = length - 1;
    while (end >= start)
    {
        int middle = ((end - start) >> 1) + start; //     ，(end + start)/2     
        int count = countRange(numbers, length, start, middle);
        if (end == start) //        
        {
            if (count > 1) //                 1
                return start; //         
            else
                break; //       ，        
        }

        if (count > (middle - start + 1)) //                     
            end = middle;  //           ，         
        else 
            start = middle + 1; //            ，         
    }
    return -1;
}


//                 
int countRange(const int* numbers, int length, int start, int end)
{
    if (numbers == nullptr)
        return 0;

    int count = 0;
    for (int i = 0; i < length; i++)
        if (numbers[i] >= start && numbers[i] <= end)
            ++count;
    return count;
}

Python

class Solution():
    def getDuplicaton(self, numbers):
        if numbers == None or len(numbers) <= 0:
            return 'valid numbers'
        start = 1
        end = len(numbers) - 1
        while(end >= start):
            middle = ((end - start) >> 1) + start
            count = self.countRange(numbers, start, middle)
            if end == start:
                if count > 1:
                    return start
                else:
                    break
            if count > (middle - start + 1):
                end = middle;
            else:
                start = middle + 1
        return 'no duplication'

    def countRange(self, numbers, start, end):
        if numbers == None:
            return 0
        count = 0
        for i in range(len(numbers)):
            if numbers[i] >= start and numbers[i] <= end:
                count += 1
        return count

s = Solution()
a = s.getDuplicaton([])
print(a)

上記のコードは二分探索の考え方に従い,長さnの配列でcountRangeはO(logn)回呼び出され,毎回O(n)の時間が必要となり,総時間複雑度はO(nlogn),空間複雑度はO(1)となる.方法1と比べると、時間で空間を変えることに相当します.
この方法では、重複するすべての数字を見つけることは保証されません.例えば、配列{2,2}の範囲1~2における数字の出現回数も2であり、重複する数字があるとは考えられない.だからテーマの特性に基づいてコードを書きます.