Algorytm zaimplementowany w ruby ​​w celu dodania go do liczby reprezentowanej jako tablica

Question

Potrzebuję porady na temat mojego rozwiązania opartego na rombach, aby rozwiązać problem z Ankiecie. Problem jest następujący

Given a non-negative number represented as an array of digits, 

add 1 to the number (increment the number represented by the digits). 

The digits are stored such that the most significant digit is at the head of the list. There can be upto 10,000 digits in the input array. 

Example: 

If the vector has [1, 2, 3] 

the returned vector should be [1, 2, 4] 

as 123 + 1 = 124. 

Moje pierwsze rozwiązanie było następująco

def plusOne(a) 
     new_number = a.join.to_i + 1 
     result = [] 
     while new_number > 0 
      result.push new_number%10 
      new_number /= 10 
     end 
     result.reverse 
end 

Algorytm ten wydaje słuszne, to przeszły wejścia testowe ale o poddaniu daje „Przekroczono limit czasowy”. Moje drugie rozwiązanie było udane i jest następujące.

def plusOne(a) 
     carry = 1 
     start_index = a.size - 1 
     temp_result = [] 
     ans = [] 

     for i in start_index.downto(0) 
      sum = a[i] + carry 
      carry = sum/10 
      temp_result.push sum%10 
     end 
     temp_result.push carry 

     start_index = temp_result.size - 1 
     while start_index >= 0 and temp_result[start_index] == 0 
      start_index -= 1 
     end 

     while start_index >= 0 
      ans.push temp_result[start_index] 
      start_index -= 1 
     end 
     ans 
    end 

Moje pierwsze rozwiązanie wydaje się być O (n) dla mnie jak jesteśmy tylko iteracja ciągu cyfr w liczbie. Czy ktoś może mi powiedzieć, dlaczego mógł przekroczyć limit czasowy?

Dziękuję

Answer 1

while new_number > 0 
    result.push new_number%10 
    new_number /= 10 
end 

Choć na pierwszy rzut oka wydaje się, że pętla O(n), to przynajmniej Ω(n²).

Ponieważ duże liczby w Ruby są przechowywane i przetwarzane jako tablice cyfr binarnych (cyfry w bazie 2³²), podział według 10 jest kosztowną operacją. Dokładna złożoność czasu zależy od algorytmu podziału używanego przez Ruby, ale new_number /= 10 będzie musiał przetworzyć wszystkie cyfry binarne new_number, więc nie może być szybszy niż O(n).

Answer 2

Rozwiązanie

Zauważ, że O (n) powinien być najgorszy scenariusz (na przykład z [9]*n).

W przypadku [1,2,3]*1000 operację można wykonać w 1 kroku, ponieważ nie ma przenoszenia i wystarczy obliczyć wartość 3+1.

W swojej pierwszej metodzie, pętla while wydaje się być bardzo droga.

Wystarczy za pomocą:

(a.join.to_i+1).to_s.chars.map{|i| i.to_i} 

jest znacznie szybsze, według fruity.

Szybsze rozwiązanie

jeśli jest to dopuszczalne, aby zmodyfikować oryginalną tablicę:

class Solution 
    # param a : array of integers 
    # return a array of integers 
    def plusOne(a) 
    a.unshift(0) 
    carry = 1 
    (a.size-1).downto(0) do |index| 
     if a[index] < 9 
     a[index] += carry 
     break 
     else 
     a[index] = 0 
     end 
    end 
    a.shift while a[0] == 0 
    a 
    end 
end 

przeszedł test na www.interviewbit.com i owocowy mi mówi, że to 45 razy szybciej niż drugiego sposobu i 180 razy szybciej niż twoja pierwsza.

Answer 3

def add_1(arr) 
    idx = arr.rindex { |n| n < 9 } 
    return [1].concat([0]*arr.size) if idx.nil? 
    arr.map.with_index do |n,i| 
    case i <=> idx 
    when -1 then n 
    when 0 then n+1 
    else 0 
    end 
    end 
end 

add_1 [1, 2, 3] 
    #=> [1, 2, 4] 
add_1 [1, 2, 9] 
    #=> [1, 3, 0] 
add_1 [1, 9, 9] 
    #=> [2, 0, 0] 
add_1 [9, 9, 9] 
    #=> [1, 0, 0, 0] 

To może być także napisany

def add_1(arr) 
    idx = arr.rindex { |n| n < 9 } 
    return [1].concat([0]*arr.size) if idx.nil? 
    (arr[0,idx] << arr[idx]+1).concat([0]*(arr.size-idx-1)) 
end 

które mogą być bardziej efektywne.