通过从给定数字中删除n位数来创建最低编号

Question

它将输入的一个数字（字符串）作为输入，然后任务是删除n个数字以给出最终可能的最小编号，但是您必须注意顺序，这是约束。您无法更改原始数字的顺序。

我希望它在O（n）的工作，所以我这样做：

#!/usr/bin/perl 
#lowestNS.pl 
#Date: 2016-06-28 

use warnings; 
use strict; 
use utf8; 

(@ARGV == 2) or die "2 args needed"; 
my $num = $ARGV[0]; 
my $d = $ARGV[1]; 
my @arr; 

int($num) > 0 or die "Enter positive number"; 

print "Number in: $num\nDel: $d\n"; 

if(int($num) == 0) { 
    print "Result: 0\n"; 
    exit; 
} 
else { 
    my $str = $num; 
    @arr = split(//, $str); #/Split on each number 
    #Split and multiply by reverse index, to give precedence to the order of numbers 
    for(my $i = 0; $i < @arr; $i++) { 
     $arr[$i] *= (@arr - $i); 
    } 
} 

print "arr: " . join(',' , @arr) . "\n"; 

for (my $j = 0; $j < $d; $j++) { 
    my $max = $arr[0]; 
    my $m_index = -1; 

    #replace nth maximum with -1 

    for (my $i = 0; $i < @arr; $i++) { 
     if($max <= $arr[$i]) { 
      $max = $arr[$i]; 
      $m_index = $i; 
     } 
    } 
    $arr[$m_index] = -1; 
} 


#return all numbers with value other than -1 

my $result = ""; 

for (my $i = 0; $i < @arr; $i++) { 
    if($arr[$i] != -1){ 
     $result = $result . "" . $arr[$i]/(@arr - $i); 
    } 
} 

print "Result: $result\n"; 

它可以在所有的情况下，除，情况类似：
Number = 765028321 Delete = 5
的问题是拆除7650 2 8321当它应该删除765028 3 21.
因为2 * 5> 3 * 3。

Answer 1

一种可能的解决方案可以是：

1. 创建的所有数字的具有阵列计数，例如。你的情况，这阵会看起来像：1,1,2,1,0,1,1,1,1,0

2. 然后，在贪婪的方式，删除所有big数字，多达可以做到的。所以，你删除了9个，但由于它的计数是0，你仍然需要删除5个数字。删除8位，所以你仍然需要删除4位数等等。

3. 这种情况是一种微不足道的，所以你会留下2 2's, 1 1's and 1 0's。在数量上也有3 4's，那么您需要删除1 4.因此，您将删除所需的最左边的部分删除。

它是一种贪婪的方法，并在O（n）中工作。

Answer 2

我认为，算法很简单：

假设，N是数字删除的号码;
1.找到前N位数字中的第一个最小的数字，删除其左边的数字，将N减去删除的位数。
2.如果N> 0将数字右移并重复上述步骤。
当然，我们需要检查边际的情况下，并确保最终数量不为0
这里是法草案开始：

#!/usr/bin/perl 
use strict; 
use warnings; 
my ($number, $del)=@ARGV; 
my @num = $number=~m{.}g; 
my $curpos=0; 
my @finalnum; 
for(;;) { 
    last if $del <=0 || $curpos+$del>=@num; 
    my $minpos=$curpos; 
    for (my $i=$curpos;$i<$curpos+$del+1 && $i < @num;$i++) { 
    if ($num[$i]<$num[$minpos] && !($curpos==0 && $num[$i]==0)) { 
     $minpos=$i; 
    } 
    } 
    push @finalnum, $num[$minpos]; 
    $del-=($minpos-$curpos); 
    $curpos=$minpos+1; 
} 
push @finalnum, @num[$curpos+$del..$#num] if $curpos+$del < @num; 
print join '', @finalnum;