주어진 숫자에서 n 개의 숫자를 제거하여 가장 낮은 숫자를 만듭니다.

Question

입력으로 숫자 (문자열)를 취한 다음 n 개의 숫자를 제거하여 가능한 가장 작은 숫자를 얻지 만 순서를 처리해야합니다. 그것은 제약 조건입니다. 원래 숫자의 순서는 변경할 수 없습니다.

이 나는 ​​O (N)에서 작업하고 싶었다, 그래서 나는이 한 : 문제는 제거하는 것이다
Number = 765028321 Delete = 5
: 같은

#!/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"; 

그것은 제외하고, 모든 경우에 작동 사례 7650 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이면 오른쪽으로 숫자를 가져 와서 위의 단계를 반복하십시오.

#!/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;