最多 K 次交换相邻数位后得到的最小整数
题目大意：
给你一个字符串 num 和一个整数 k 。其中，num 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个 数位 。
你可以交换这个整数相邻数位的数字 最多 k 次。
请你返回你能得到的最小整数，并以字符串形式返回。
题解
贪心，每次将最小的数移动到当前字符串的最前端，判断能否移动。每次移动后，字符串都会改变（长度较少1），因此最基本的思路就是我们可以从最小的数字递归的进行计算
def minInteger(self, num: str, k: int) -> str:
if k<=0 or not num:
return num
for i in range(10):
index=num.find(str(i))
if index < 0:
continue
if index<=k:
if index==k:
return str(i)+num[0:index]+num[index+1:]
else:
return str(i)+self.minInteger(num[0:index]+num[index+1:],k-index)
但是上述的时间复杂度为O(n^2)，虽然可以过，但显然不够好
分析上述算法的过程我们可以发现，每次字符串查找的复杂度都是O(n)。我们可以用树状数组或字典树存储在当前置换位置i的前面有多少已经置换过了，这样我们只需要log(n)次查询（相当于区间求和）
int n;
int f[30010];
int a[30010];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int v)
{
while(x<=n)
{
f[x]+=v;
x+=lowbit(x);
}
}
int query(int x)
{
int res=0;
while(x>=1)
{
res+=f[x];
x-=lowbit(x);
}
return res;
}
string minInteger(string num, int k) {
n=num.length();
for(int i=1;i<=n;i++)a[i]=num[i-1]-'0',f[i]=0;
vector<int>v[10];
for(int i=1;i<=n;i++)
{
v[a[i]].push_back(i);
add(i,1);
}
string ans="";
for(int i=0;i<10;i++)
reverse(v[i].begin(),v[i].end());
int cur;
while(ans.size()<n)
{
for(int i=0;i<10;i++)
{
if(v[i].size()>0)
{
int cur=query(v[i].back())-1;
if(cur<=k)
{
k-=cur;
ans+=i+'0';
add(v[i].back(),-1);
v[i].pop_back();
break;
}
}
}
}
return ans;
有一个实现细节需要注意，每次我们都是从小到大寻找数字的，如果较大的数在前面，可能在某一论中较小的数无法置换。但是当该较大的数访问后，之前较小的数又可以置换。因此我们每次置换后，都需要从0开始，如果加个判断条件，时间复杂度依然是O(n^2)。因此我们可以利用vector不断的剔除置换过的数字，这样将减少重复访问的次数。