LeetCode 1505. 最多 K 次交换相邻数位后得到的最小整数

Categories:

题目描述
思路分析
1. 解法一：贪心 + 树状数组（推荐）
相似题目

题目描述

✅ 1505. 最多 K 次交换相邻数位后得到的最小整数

思路分析

解法一：贪心 + 树状数组（推荐）

核心思路：

维护每个数字在字符串中的所有位置队列。

每次从 0~9 尝试能否将某数字移动到当前位置，成本为实际位置减去已移除数量。

使用树状数组统计已移除数量，贪心构造字典序最小结果。

复杂度分析：

时间复杂度：O(n log n)。

空间复杂度：O(n)。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String minInteger(String num, int k) {
        int n = num.length();
        Deque<Integer>[] pos = new Deque[10];
        for (int i = 0; i < 10; i++) {
            pos[i] = new ArrayDeque<>();
        }

        for (int i = 0; i < n; i++) {
            pos[num.charAt(i) - '0'].add(i + 1);
        }

        Fenwick bit = new Fenwick(n);
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            for (int d = 0; d <= 9; d++) {
                if (pos[d].isEmpty()) {
                    continue;
                }

                int idx = pos[d].peekFirst();
                int moved = bit.query(idx);
                int cost = idx - 1 - moved;

                if (cost <= k) {
                    k -= cost;
                    sb.append((char) ('0' + d));
                    bit.add(idx, 1);
                    pos[d].pollFirst();
                    break;
                }
            }
        }

        return sb.toString();
    }

    private static class Fenwick {
        private final int[] tree;

        Fenwick(int n) {
            tree = new int[n + 1];
        }

        void add(int idx, int delta) {
            while (idx < tree.length) {
                tree[idx] += delta;
                idx += idx & -idx;
            }
        }

        int query(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }
}

func minInteger(num string, k int) string {
	n := len(num)
	pos := make([][]int, 10)
	for i := 0; i < n; i++ {
		d := int(num[i] - '0')
		pos[d] = append(pos[d], i+1)
	}

	bit := newFenwick(n)
	res := make([]byte, 0, n)

	for i := 1; i <= n; i++ {
		for d := 0; d <= 9; d++ {
			if len(pos[d]) == 0 {
				continue
			}
			idx := pos[d][0]
			moved := bit.query(idx)
			cost := idx - 1 - moved
			if cost <= k {
				k -= cost
				res = append(res, byte('0'+d))
				bit.add(idx, 1)
				pos[d] = pos[d][1:]
				break
			}
		}
	}

	return string(res)
}

type Fenwick struct {
	tree []int
}

func newFenwick(n int) *Fenwick {
	return &Fenwick{tree: make([]int, n+1)}
}

func (f *Fenwick) add(idx int, delta int) {
	for idx < len(f.tree) {
		f.tree[idx] += delta
		idx += idx & -idx
	}
}

func (f *Fenwick) query(idx int) int {
	sum := 0
	for idx > 0 {
		sum += f.tree[idx]
		idx -= idx & -idx
	}
	return sum
}

相似题目

题目	难度	考察点
1505. 最多 K 次交换相邻数位后得到的最小整数	困难	贪心、树状数组
402. 移掉K位数字	中等	贪心
1673. 找出最具竞争力的子序列	中等	单调栈
321. 拼接最大数	困难	贪心
1856. 子数组最小乘积的最大值	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/95431037