座標圧縮
(compression/array_compression.py)

• View this file on GitHub
• Last update: 2023-10-09 20:06:19+09:00

概要

座標圧縮を行います。

計算量

• 未解析（後で書きます。）

補足

Pythonならmap関連の動作が早いので、これでも通る。 Python : array_compression.py N = int(input()) A = list(map(int, input().split())) sorted_unique_A = sorted(set(A)) coordinate_map = {value: index + 1 for index, value in enumerate(sorted_unique_A)} B = [coordinate_map[a] for a in A] print(*B)

Code

# 二分探索の定義
def binary_search(array, target):
    left, right = 0, len(array) - 1

    while left <= right:
        mid = (left + right) // 2

        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


N = int(input())
A = list(map(int,input().split()))

# 座標圧縮後の配列の定義
B = [0]*N

# 元の配列の重複を削除し、ソートした配列Tの宣言
T = list(set(A))
T.sort()

for i in range(N):
    B[i] = binary_search(T,A[i])
    B[i] += 1
print(*B)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.1/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.1/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page