1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| from collections import deque
class Solution:
def minInteger(self, num: str, k: int) -> str:
pqs = [deque() for _ in range(10)]
for i in range(len(num)):
pqs[int(num[i])].append(i)
ans = ""
seg = SegmentTree(len(num))
for i in range(len(num)):
for digit in range(10):
if pqs[digit]:
pos = pqs[digit][0]
shift = seg.getCountLessThan(pos)
if pos - shift <= k:
k -= pos - shift
seg.add(pos)
pqs[digit].popleft()
ans += str(digit)
break
return ans
class SegmentTree:
def __init__(self, max):
self.nodes = [0] * (4 * max)
self.n = max
def add(self, num):
self.addUtil(num, 0, self.n, 0)
def addUtil(self, num, l, r, node):
if num < l or num > r:
return
if l == r:
self.nodes[node] += 1
return
mid = (l + r) // 2
self.addUtil(num, l, mid, 2 * node + 1)
self.addUtil(num, mid + 1, r, 2 * node + 2)
self.nodes[node] = self.nodes[2 * node + 1] + self.nodes[2 * node + 2]
def getCountLessThan(self, num):
return self.getUtil(0, num, 0, self.n, 0)
def getUtil(self, ql, qr, l, r, node):
if qr < l or ql > r:
return 0
if ql <= l and qr >= r:
return self.nodes[node]
mid = (l + r) // 2
return self.getUtil(ql, qr, l, mid, 2 * node + 1) + self.getUtil(ql, qr, mid + 1, r, 2 * node + 2)
|