探索に関するアルゴリズムの課題

9.1 線形探索と二分探索を用いた問題の例

線形探索

配列内の要素を探す課題: 数字の配列と目標値が与えられています。配列内での目標値のインデックスを見つける必要があります。

解決法: 配列の各要素を確認するために線形探索を使います。

実装例:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# 使用例:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # 出力: 2

二分探索

ソートされた配列内の要素を探す課題: ソートされた数字の配列と目標値が与えられています。配列内での目標値のインデックスを見つける必要があります。

解決法: 配列を半分に分けて目標値を探すために二分探索を使います。

実装例:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 使用例:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # 出力: 3

9.2 探索を最適化するためのハッシュテーブルの利用課題

1. 配列内の重複を探す

課題: 数字の配列が与えられています。配列内のすべての重複を見つけて返す必要があります。

解決法: すでに見かけた数字を追跡するためにハッシュテーブルを使います。数字が再度現れた場合、それを重複リストに追加します。

実装例:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用例
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 出力: [2, 4]

2. 指定した和を持つペアを見つける

課題: 数字の配列と目標の合計値が与えられています。目標値を合計として持つすべての数字のペアを見つける必要があります。

解決法: 数字を保存し、現在の数字とペアを作って目標の和を持つかどうかを確認するためにハッシュテーブルを使用します。

実装例:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# 使用例
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 出力: [(1, 5), (7, -1), (1, 5)]

9.3 様々な探索手法の組み合わせの使用

複雑な課題では、最良の効率を達成するためにいくつかの探索手法を使用する必要があります。線形探索、二分探索、ハッシュテーブルの組み合わせで、より効率的かつ柔軟に課題を解決できます。

例1: 配列内の要素を探し、別の配列での存在を確認する

2つの数字の配列が与えられています。2番目の配列に存在する最初の配列の要素を見つける必要があります。

解決法:

• 2番目の配列の要素を保存するためにハッシュテーブルを使用します。
• 最初の配列の各要素について、そのハッシュテーブルでの存在を確認します。

実装例:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # 2番目の配列用ハッシュテーブル
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# 使用例:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # 出力: [3, 4, 5]

例2: ハッシュテーブルを使用したアナグラム配列確認

文字列の配列とパターン文字列が与えられています。文字列の配列内の部分文字列がパターンのアナグラムであるかどうかを確認する必要があります。

解決法:

• パターンの文字頻度を数えるためにハッシュテーブルを使います。
• 文字列の配列を走査し、各部分文字列の文字頻度を「スライドウィンドウ」で確認します。

実装例:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# 使用例:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # 出力: True

9.4 内容を定着させるための実践課題

課題1: 未ソート配列内の要素を探す

数字の配列と目標値が与えられています。配列内での目標値のインデックスを見つける必要があります。線形探索を使用すること。

実例:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# 使用例:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # 出力: 2

課題2: 配列内の重複を見つける

数字の配列が与えられています。ハッシュテーブルを使用して配列内のすべての重複を見つけて返す必要があります。

実例:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用例:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # 出力: [3, 1]