[規格18870]座標圧縮(Python/Python)

5971 ワード
白駿 Python3 テキストリンク

問題の概要


N個の座標を与えます.
Xiを座標圧縮すると、Xiより小さい座標値から重複する座標を除外し、異なる座標の個数だけ出力することができます.

に答える


初めての試み

  • X座標を入力し、setを使用して重複する値を除去します.
  • Xsetを並べます.
  • X座標を巡回し、Xsetにindexを出力します.
    • このコードは.indexの最悪の場合にO(n)O(n)O(n)O(n)O(n))の時間的複雑度を有するため、全体的にO(n 2)O(n^2)O(n 2)の時間的複雑度となる.nは最大100万なので、もちろんタイムアウトが発生します.
    n = int(input())

Xs = list(map(int,input().split()))

setX = sorted(list(set(Xs)))

res = []
for x in Xs :
  compression = setX.index(x)
  res.append(str(compression))

print(' '.join(res))

    二次試行


    O(nlogn)O(nlogn)O(nlogn)O(nlogn)の時間的複雑さを達成できる.
    したがって、ソートを使用できます.上記の過程で、1、2番は3万を修正します.
    indexを使用しないで、どのようにO(n)O(n)O(n)あるいはO(1)O(1)O(1)O(1))の中でindexを探し当てて、この時dictionaryを使って一回捜索することができることを思い付きました.
  • dictionaryに変更し、O(1)O(1)O(1)をナビゲートします.
    n = int(input())

Xs = list(map(int,input().split()))

setX = sorted(list(set(Xs)))
dictX = dict()
for i in range(len(setX)) :
  dictX[setX[i]] = i

res = []
for x in Xs :
  res.append(str(dictX[x]))
print(' '.join(res))
    • CompletableFuture同時プログラミング能力の向上
    [Programmers] 5week