配列内で繰り返される数字(Python and C++解法)

タイトル:
長さnの配列のすべての数字は0からn-1の範囲内にある.配列のいくつかの数字は重複していますが、いくつかの数字が重複していることは分かりません.数字ごとに何回繰り返されるか分からない.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力すると、最初の繰り返しに対応する数字は2である.
ソース:https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&&tqId=11203&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
考え方:
1つ目の考え方:重複する数字を探すのが最も考えやすいのは、数字が重複している場合、並べ替え後の隣接する数字は必ず同じであるが、並べ替えアルゴリズムの時間複雑度はO(n*logn)であるため、先に並べ替えた後に検索することである.
第2の考え方:ハッシュテーブルを用いて配列を遍歴する際,ハッシュテーブル内にその数字が含まれているか否かを判断し,もしなければハッシュテーブルを加え,あれば重複する数字を見つけ,この方法は配列を1回遍歴するだけであるが,O(n)の空間的複雑さが必要である.
第3の考え方:テーマから与えられた情報を十分に利用し、配列が重複していない場合、下付きiにスキャンすると、配列値もiであるべきである.
重複する数字がある場合は、まずiと表記された数字(x)がiに等しいかどうかを比較し、等しい場合は次の数字に遍歴する.等しくなければ、下付きxのデータと比較し、等しい場合は重複する数字を見つけ、等しくなければ、下付きiの数字と下付きxの数字を交換し、下付きiの数字xを正しい位置に置き、上記の手順を繰り返す. 
Python解法(考え方2):

 1 class Solution:
 2     def duplicate(self, numbers, duplication):
 3         if numbers is None or len(numbers) <= 0:  #       
 4             return False
 5         for i in range(len(numbers)):  #       
 6             if numbers[i] < 0 or numbers[i] > len(numbers)-1:
 7                 return False
 8         hash_table = []
 9         for i in range(len(numbers)):
10             if numbers[i] not in hash_table:
11                 hash_table.append(numbers[i])
12             else:
13                 duplication[0] = numbers[i]
14                 return True
15         return False

C++解法(思路三):

 1 class Solution {
 2 public:
 3     bool duplicate(int numbers[], int length, int* duplication) {
 4         if (numbers == NULL || length <= 0)  //       
 5             return false;
 6         for (int i = 0; i < length; i++) //       
 7             if (numbers[i] < 0 || numbers[i] > length - 1)
 8                 return false;
 9         for (int i = 0; i < length; i++) {
10             while (numbers[i] != i) {  //      i     i，            
11                 if (numbers[i] == numbers[numbers[i]]) {  //     i       numbers[i]     
12                     *duplication = numbers[i];
13                     return true;
14                 } 
15                 else {
16                     int swapTemp = numbers[i];
17                     numbers[i] = numbers[swapTemp];  // numbers[i] = numbers[numbers[i]]       
18                     numbers[swapTemp] = swapTemp;
19                 }
20             }
21         }
22         return false;
23     }
24 };