给定正整数(以数字数组的形式).我们被允许交换给定数字中的一对数字.我们需要返回可以获得的最小可能整数.注意,它应该是一个有效的整数,即不应该包含前导0.
例如:-
是否有O(n)针对此问题的算法.我想到了几个方法: -
minDIgit给定整数中的digit()(0除外)并将其与MSB交换,如果MSB != minDigit.如果MSB==minDigit,那么找到下一分钟.数字并用最重要但1位数字交换它,依此类推.这可能是O(n^2)最糟糕的情况.array/vector的std::pair数字和索引的,并以递增顺序排序(按数位值;保持低指数的第一匹配数字值).遍历排序的数组.用第一个数字交换MSB.如果最小数字具有相应的索引作为MSB,则交换MSB但是将1个位置与下一个最小数字交换.如果下一个最小数字具有相应的MSB索引但是1个位置,那么交换MSB但是在下一个min处交换2个位置.数字等.这应该是O(nlog(n)).有人可以建议更好的算法.
更新1:
经过一番思考后,我提出的第二个算法将完美地工作(可能除了少数角落情况,可以单独处理).此外,我可以使用计数排序(根据数字值)对对(数字,索引)进行排序,这是一种稳定的O(n)时间排序.我的论点有缺陷吗？
更新2:
我的第二个算法会工作(虽然有更多的角落情况和0的检查),而且也是O(n)时间counting sort.但是@GaborSch提供的解决方案要简单得多,所以我不会真的为我的算法提供合适的代码.
gab*_*sch 18
作为准备,我们遍历数字,并标记数组[10](称之为)(包括s)中数字的最后位置.那是O(n).last0
接下来,我们开始从左到右迭代数字.对于每个位置,我们尝试找到最后位置大于当前位置(位置约束)的最小数字.该数字也必须小于当前数字.
如果我们处于第一个位置,我们last从1(或者从0)开始循环,直到当前数字的值(不包括).
如果我们找到这样一个数字(关于位置约束),我们交换(并打破循环).如果我们不这样做,我们会前进到下一个数字.成本至多为O(n*9),即O(n).
总成本是O(n)+ O(n)*O(9)= O(n).
算法如何处理示例:
93561 -> it can swap in the first cycle
596 -> skipping the first cycle,
then finds '6' because of the position constraint
(comparing position '1' with last[5] = 0, last[6] = 2)
10234 -> does not find anything because of the position constraint
93218910471211292416 -> finds the last occurrence of '1' to replace '9'
98761111 -> it can swap in the first cycle
(last[1] = 7, so it will change the last occurrence)
555555555555555555596 -> iterates until the '9', then you skip last[5]
but finds last[6] as a good swap
120 -> at pos 0 (1) cannot find a non-zero element less than 1, so skip
at pos 1 (2) can find 0 on position 2, so we swap
再一次,在这里我们对数字进行一次迭代(用于预解析数据),然后进行一次迭代以找到MSB.在第二次迭代中,我们迭代last,这是恒定大小(最多9).
您可以通过在值开始循环时添加跟踪最小值来进一步优化算法last,但这已经是优化.prevoius版本包含,检查历史记录,如果你感兴趣:)
Kar*_*ath 11
First count each digit, store it in an array (counts[10]).
Going from the left, check the digits (following is the description of the loop):
Check that there's a digit in counts which is smaller than it. Pick the smallest one. Exception: 0 is not allowed for the very first digit.
counts, and go for the next digit.For each digit you do O(1) work. So the whole algo is O(n).
For swapping you want to use the least significant digits (furthers to the right). You can either store these locations on the initial lookup, or just before swapping you can search for the first matching digit starting from the end.
我会从右端开始迭代数组.将数字存储在右侧作为最小数字和最大数字并开始向左移动,如果您点击一个新的较小数字,则将其称为最小数字.如果你继续向左移动并找到一个较小的数字,那么将较小的数字设为潜在的数字.如果找到一个更大的数字,可以使最小的int小一些,并将较大的一个存储为最大数字.每当你达到比最小数字更大的数字时,将其设为新的最大数字.如果你到了最后,交换最大数字和最小数字.在python中(这是有效的,是O(n))
def swap_max(digits):
i = len(digits) - 1
while i > 0:
if digits[i] == 0:
i-= 1
else:
break
max_i = i
min_i = i
pot_i = i
z_i = -1
nz_i = i
i = len(digits) - 1
while i >= 0:
if digits[i] > digits[pot_i]:
max_i = i
min_i = pot_i
if digits[i] < digits[min_i] and digits[i] != 0:
pot_i = i
if digits[i] == 0 and z_i == -1:
z_i = i
if digits[i] != 0 and i > 0:
nz_i = i
i -= 1
if z_i != -1 and max_i != 0 and max_i < z_i:
min_i = z_i
i = nz_i
max_i = i
elif max_i == min_i and z_i != -1:
i = nz_i
if i < z_i:
min_i = z_i
max_i = i
v = digits[min_i]
digits[min_i] = digits[max_i]
digits[max_i] = v
return digits
#TESTING THE FUNCTION
tests = [93561,596,10234,120,10091,98761111,1001,1010,1103,120,93218910471211292416]
results = [13569,569,10234,102,10019,18761119,1001,1001,1013,102,13218910471211292496]
tests = map(list,map(str,tests))
results = map(list,map(str,results))
for i in range(len(tests)):
res ="".join(map(str,swap_max(map(int,tests[i]))))
print res,"".join(results[i])
if res=="".join(results[i]):
print "PASSED\n"
else:
print "FAILED\n"
这最终适用于所有示例.它还具有O(1)内存使用的优点.