Problem z zadaniem opartym na tablicach.

0

Cześć, jestem początkującym w programowaniu. Korzystam ze strony którą udostępnia zadania do robienia. Natknąłem się teraz z zadaniem z którym mam problem. Treść zadania skrócę i opiszę własnymi słowami. Dostajemy statuetki o danych rozmiarach (int) i zadanie prosi nas o podanie nam na wyjściu jakich statuetek brakuje aby mogły one być ułożone w kolejności. Przykład "For statues = [6, 2, 3, 8] wyjście powinno mieć wartość 3, ponieważ brakuje 4,5,7"
Przykład 2 " statues= [3, 0] wyjście powinno mieć wartość 2, ponieważ brakuje 1, 2". Przykład 3 "statues=[4, 5, 6] wyjście powinno mieć wartość 0, ponieważ nie brakuje żadnej".
Mój kod, który nie działa do wszystkich danych wejściowych:

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
	    int var = 0;
	    int[] statues = {6,2,3,8};
	    Arrays.sort(statues);
	    for(int i=0; i < statues.length-1; i++){
		if(statues[i+1] - statues[i] != 1){
		    int k = statues[i+1] - statues[i];
		    var = var + k-1;
		    i++;
	        }
    	}
    	System.out.println(var);
    }
}

Bardzo proszę o pomoc w rozwiązaniu tego zadania.

2

Ja bym spróbował tak:

  • corner case: tablica jednoelementowa - zwróć 0;
  • znależć maksimum, minimum i długość - O(n);
  • między minimum a maksimum powinno być: t = maksimum - minimum - 1 elementów, i zwracamy t - (długośc - 2) - złożonośćO(1)
    Całkowita złożoność O(n). Dla pierwszego przykładu zwróć: 8 - 2 - 1 - 4 + 2 = 3.
0

Linka podać nie moge bo trzeba mieć konto i dojść do tego zadania rozwiązując poprzednie. Tutaj podsyłam pełną treść po angielsku(po polsku nie ma).

Ratiorg got statues of different sizes as a present from CodeMaster for his birthday, each statue having an non-negative integer size. Since he likes to make things perfect, he wants to arrange them from smallest to largest so that each statue will be bigger than the previous one exactly by 1. He may need some additional statues to be able to accomplish that. Help him figure out the minimum number of additional statues needed.

Example

For statues = [6, 2, 3, 8], the output should be
makeArrayConsecutive2(statues) = 3.

Ratiorg needs statues of sizes 4, 5 and 7.

Input/Output

[execution time limit] 3 seconds (java)

[input] array.integer statues

An array of distinct non-negative integers.

Guaranteed constraints:
1 ≤ statues.length ≤ 10,
0 ≤ statues[i] ≤ 20.

[output] integer
    The minimal number of statues that need to be added to existing statues such that it contains every integer size from an interval [L, R] (for some L, R) and no other sizes.
0

OK, Zaimplementowałeś algorytm, który Ci podałem?

0

Tak, wszystko działa, dziękuje bardzo za pomoc. Męczyłem się długo z tym zadaniem, które tak naprawdę jest banalne. Jeszcze raz dzięki :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1