与えられた数字から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
問題が除去されます765028 3 21.
2 * 5> 3 * 3であるため、7650 2 8321を削除する必要があります。

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;