通過從給定數字中刪除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;