배열의 m 번째 요소를 삭제하십시오.

Question

크기가 n 인 배열이 주어지면 배열에 하나의 요소 만 존재하고 그 값을 반환 할 때까지 배열의 모든 m 번째 요소를 삭제하는 함수를 작성해야합니다. 누군가 나에게 힌트를 줄 수 있습니까?

Answer 1

순진 방법은 그것을 할 수 있습니다 :

• 시작 요소 m에서 포인터에 의해 내가 원하지 않기 때문에 새로운를 재구성해야 할,이 마커를 넣어 의미 삭제 (삭제 배열을 삭제할 때마다 배열)
• 포인터를 증가 시키십시오 m 번. 삭제 된 요소를 가리키는 경우 카운터를 1 줄여서 m 이전 항목으로 이동하십시오. 배열 끝에서 벗어나면 0 위치로 다시 이동하십시오.
• 삭제 한 항목 수를 기록하십시오. n-1 이후에 중지하십시오.

Answer 2

python에서는 실제로 항목을 삭제하는 대신 실행마다 목록을 재구성합니다. 아마도 더 잘할 수있을 것입니다.

이것은 첫 번째 (0 번째) 항목이 처음으로 이동해야한다는 것을 고려합니다. 당신이 해결하려고하는 것처럼

def lms(l, m, r=0): 
    """Return last man standing in the lineup l where every mth man is 
    executed.""" 
    if len(l) == 1: return l[0] 
    return lms(
     [l[x] for x in range(len(l)) if (r + x) % m], # new list without exec. 
     m,           # frequency 
     (r + len(l)) % m)        # remainder from this round 

def get_lms(n, m): 
    """Just a setup function, which creates a plain range list to serve to the function. 
    Any list of any items can be used.""" 
    l = [x for x in range(n)] 
    return lms(l, m) 

>>> get_lms(10, 3): 
3 

Answer 3

는 소리 Josephus Problem :

실행을 기다리고 원 에 서있는 사람들이있다

. 첫 번째 사람이 실행 된 후 특정 숫자 명이 건너 뛰고 한 명의 사람이 으로 실행됩니다. 그런 다음 다시 사람들은 을 건너 뛰고 사람이 처형됩니다. 제거는 동그라미 (처형 된 사람들이 제거됨에 따라 이 작아짐), , 마지막 사람 만 남을 때까지 에게 자유가 주어질 때까지 진행됩니다.

작업은 (남은 마지막 것)이되도록 초기 서클에서 장소를 선택하는 것입니다.

위키 기사는 위의 문제에 대한 매우 간단한 재귀 솔루션을 포함 할 수 n은 사람들의 수는 K = 사람들은, 삭제 당 건너 :

f(1, k) = 0 
f(n, k) = (f(n - 1, k) + k) % n 

Answer 4

내가 구현하기 위해 노력했다. .bt 높은 복잡성을

public static void DeleteM(int[] arr, int m) 

    { 
     int k = m; 
     int count = 0; 
     while (count<arr.Length-1) 
     { 
      if (m < arr.Length && arr[m]!=-1) 
      { 
        arr[m] = -1; //Mark it 
        count++;//Set the marked count 
        m = m + k; 
      } 
      else 
      { 
       int i = 0; 
       if (arr[i] == -1) 
       { 
        while (arr[i] == -1 && i < arr.Length) 
        { 
         i++; 
        } 
       } 
       m = i; 

      } 

     } 
     for(int i=0;i<arr.Length;i++) 
      if (arr[i] != -1) Console.WriteLine(arr[i]); 
    } 

Answer 5

n,k=map(int,raw_input().split()) 
ans=0 
for i in range(1,n+1): 
    ans=(ans+k)%i 
print ans+1 

Answer 6

사용이 기능이이 answer를 참조 할 것.

도움이 되길 바랍니다.

function removeAtNth($array, $nth) 
{ 
    $step = $nth - 1;  //gaps between operations 
    $benchmark = 0;  
    while(isset($array[1])) 
    { 
     $benchmark += $step; 
     $benchmark = $benchmark > count($array) -1 ? $benchmark % count($array) : $benchmark; 
     unset($array[$benchmark]); 
     $array = array_values($array); 
     echo implode('', $array)."\n"; 
    } 
} 

시험 :

$array = [1,2, 3,4,5,6,7,8]; 
removeAtNth($array, 3); 

결과 :

kris-roofe@krisroofe-Rev-station:~$ php test.php 
1245678 
124578 
24578 
2478 
478 
47 
7