W macierzy zerojedynkowej M[n][m] potrzebuje znaleźć takie x, że, M[x][1], M[x][2], ..., M[x][m-1] są równe 0, natomiast M[1][x], M[2][x], ..., M[x-1][x], M[x+1][x], ..., M[n-1][x] są równe 1. Jak mógłbym to zrobić?
0
0
Przeglądając po prostu tą macierz? Dla każdego X z zakresu 0..min(n,m) iterujesz sobie po kolejnych kolumnach wiersza X. Dodatkowo usuwamy od razu z tego zbioru potencjalnych X wartość odpowiadającą kolumnie gdzie znaleźliśmy naszą 1.
Po przeglądnięciu wszystkich elementów w zbiorze X pozostaną nam tylko te szukane X.
Dla O(nlogn) musimy iterować po elementach naszego seta w obu pętlach.
0
To tak, ten pomysł jest trywialny, jednak chciałbym znaleźć rozwiązanie w O(n). Chyba zapomniałem dodać - macierz jest kwadratowa.
0
Tak to się nie da. Chyba że wolno ci wykonywać jakieś operacje jeszcze w trakcie wczytywania danych wejściowych?
Rozwiązanie o którym pisałem wyżej da O(nlogn) dla przypadku pesymistycznego i nie wydaje mi się żeby dało się szybciej.
0
Jako, że @Shalom jest zdania, że poniżej liniowo logarytmicznego rozwiązania nie da się zejść, nie jestem pewien, czy zrozumiałem problem. W zasadzie wydaje mi się, że go nie zrozumiałem... Ale jeśli tak to:
Zliczenie jedynek w każdym wierszu i każdej kolumnie jest liniowe od elementów macierzy. Warunkiem koniecznym istnienia szukanego x, jest istnienie dokładnie jednej kolumny z zerem jedynek. Jeśli taka istnieje to warunkiem dostatecznym istnienia szukanego x jest istnienie wiersza z m-1 jedynkami.
Reszta jest chyba oczywista. Można też łatwo to wykorzystać do dynamicznego odnajdywania takich x w pesymistycznym czasie liniowym od liczby wierszy, gdy macierz się zmienia.
0
@Tacet potrafisz w macierzy NxN policzyc ile jest jedynek przeglądając tylko N elementów ewentualnie K*N gdzie K<<N? Szacun, bo ja nie potrafię. Dlatego też pytałem czy może wykonywać jakieś operacje w trakcie czytania danych na przykład, bo wtedy można by to zliczanie przeprowadzić w trakcie czytania. Ale jeśli nie można to nic z tego.
Bo jasne że można to zrobić w O(N*N), to trywialne - zliczyć czy jedynek w kolumnie x jest N-1 i sprawdzić czy macierz[x][x]==0. Ale chyba jednak nie o to chodziło ;]