golang 解法, 执行用时: 200 ms, 内存消耗: 13.7 MB, 提交时间: 2023-10-09 10:29:33

func minInteger(num string, k int) (ans string) {
    n := len(num)
    pos := [10][]int{}
    for i, v := range num {
        pos[v - '0'] = append(pos[v - '0'], i+1)
    }
    t := make(seg, n*4)		
	t.build(nil, 1, 1, n)
    for i := 1; i <= n; i++ {
        for j := 0; j < 10; j++ {
            if len(pos[j]) != 0 {
                behind := t.query(1,pos[j][0], n)
                dist := pos[j][0] + behind - i
                if dist <= k {
                    t.update(1, pos[j][0], 0)
                    pos[j] = pos[j][1:]
                    ans += string(j + '0')
                    k -= dist
                    break
                }
            }
        }
    }
    return 

}

// 线段树
type seg []struct {
	l, r int
	val  int
}

// 单点更新：build 和 update 通用
func (t seg) set(o, val int) {
	t[o].val = val
}

// 合并两个节点上的数据：maintain 和 query 通用
// 要求操作满足区间可加性
// 例如 + * | & ^ min max gcd mulMatrix 摩尔投票 最大子段和 ...
func (seg) op(a, b int) int {
	return a + b
}

func (t seg) maintain(o int) {
	lo, ro := t[o<<1], t[o<<1|1]
	t[o].val = t.op(lo.val, ro.val)
}

func (t seg) build(a []int, o, l, r int) {
	t[o].l, t[o].r = l, r
	if l == r {
		//t.set(o, a[l-1])
		return
	}
	m := (l + r) >> 1
	t.build(a, o<<1, l, m)
	t.build(a, o<<1|1, m+1, r)
	t.maintain(o)
}

// o=1  1<=i<=n
func (t seg) update(o, i, val int) {
	if t[o].l == t[o].r {
        t[o].val++
		return
	}
	m := (t[o].l + t[o].r) >> 1
	if i <= m {
		t.update(o<<1, i, val)
	} else {
		t.update(o<<1|1, i, val)
	}
	t.maintain(o)
}

// o=1  [l,r] 1<=l<=r<=n
func (t seg) query(o, l, r int) int {
	if l <= t[o].l && t[o].r <= r {
		return t[o].val
	}
	m := (t[o].l + t[o].r) >> 1
	if r <= m {
		return t.query(o<<1, l, r)
	}
	if m < l {
		return t.query(o<<1|1, l, r)
	}
	vl := t.query(o<<1, l, r)
	vr := t.query(o<<1|1, l, r)
	return t.op(vl, vr)
}

python3 解法, 执行用时: 1968 ms, 内存消耗: 18 MB, 提交时间: 2023-10-09 10:28:51

class BIT:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)
    
    @staticmethod
    def lowbit(x: int) -> int:
        return x & (-x)
    
    def update(self, x: int):
        while x <= self.n:
            self.tree[x] += 1
            x += BIT.lowbit(x)
    
    def query(self, x: int) -> int:
        ans = 0
        while x > 0:
            ans += self.tree[x]
            x -= BIT.lowbit(x)
        return ans

    def queryRange(self, x: int, y: int) -> int:
        return self.query(y) - self.query(x - 1)


class Solution:
    def minInteger(self, num: str, k: int) -> str:
        n = len(num)
        pos = [list() for _ in range(10)]
        for i in range(n - 1, -1, -1):
            pos[ord(num[i]) - ord('0')].append(i + 1)
        
        ans = ''
        bit = BIT(n)
        for i in range(1, n + 1):
            for j in range(10):
                if pos[j]:
                    behind = bit.queryRange(pos[j][-1] + 1, n)
                    dist = pos[j][-1] + behind - i
                    if dist <= k:
                        bit.update(pos[j][-1])
                        pos[j].pop()
                        ans += str(j)
                        k -= dist
                        break
        
        return ans

java 解法, 执行用时: 37 ms, 内存消耗: 43.7 MB, 提交时间: 2023-10-09 10:27:44

class Solution {
    public String minInteger(String num, int k) {
        int n = num.length();
        Queue<Integer>[] pos = new Queue[10];
        for (int i = 0; i < 10; ++i) {
            pos[i] = new LinkedList<Integer>();
        }
        for (int i = 0; i < n; ++i) {
            pos[num.charAt(i) - '0'].offer(i + 1);
        }
        StringBuffer ans = new StringBuffer();
        BIT bit = new BIT(n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 10; ++j) {
                if (!pos[j].isEmpty()) {
                    int behind = bit.query(pos[j].peek() + 1, n);
                    int dist = pos[j].peek() + behind - i;
                    if (dist <= k) {
                        bit.update(pos[j].poll());
                        ans.append(j);
                        k -= dist;
                        break;
                    }
                }
            }
        }
        return ans.toString();
    }
}

class BIT {
    int n;
    int[] tree;

    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public static int lowbit(int x) {
        return x & (-x);
    }

    public void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }

    public int query(int x) {
        int ans = 0;
        while (x > 0) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }

    public int query(int x, int y) {
        return query(y) - query(x - 1);
    }
}

cpp 解法, 执行用时: 80 ms, 内存消耗: 10.4 MB, 提交时间: 2023-10-09 10:27:14

// 贪心 + 树状数组
class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int _n): n(_n), tree(_n + 1) {}

    static int lowbit(int x) {
        return x & (-x);
    }
    
    void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }

    int query(int x) const {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }

    int query(int x, int y) const {
        return query(y) - query(x - 1);
    }
};

class Solution {
public:
    string minInteger(string num, int k) {
        int n = num.size();
        vector<queue<int>> pos(10);
        for (int i = 0; i < n; ++i) {
            pos[num[i] - '0'].push(i + 1);
        }
        string ans;
        BIT bit(n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 10; ++j) {
                if (!pos[j].empty()) {
                    int behind = bit.query(pos[j].front() + 1, n);
                    int dist = pos[j].front() + behind - i;
                    if (dist <= k) {
                        bit.update(pos[j].front());
                        pos[j].pop();
                        ans += (j + '0');
                        k -= dist;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};