求 n * n 方陣中，(1)橫、(2)縱、(3)正對角、(4)反對角 皆無相同元素之排列。 不知該怎麼下手,可否給我個idea呢?

引言: 求 n * n 方陣中，(1)橫、(2)縱、(3)正對角、(4)反對角 皆無相同元素之排列。 不知該怎麼下手,可否給我個idea呢?

okeyla你好< >: 這個問題直覺會去查一下 >!反正矩陣運算如果有什麼特殊解法的話,線性代數矩陣的部份應該都有跡可尋!離散的書也可以找找看! (<>>這個字應該是拼錯了,可是我手邊沒書查< >)! 另外土法也一定行的啦! 以一橫行為例,把這一行的>> 排序完再花<>O(n)的時間check有沒有任兩element相同! 所以做任n個elements是否有相同元素的time complexity--> O(nlogn) and O(n) ---> O(nlogn) 一個n by n的matrix共要checkn個橫行,n個直行,2個正反對角線

共2n 2次!

所以total time complexity是

  (2n 2)*nlogn -->  O(n^2log(n))  

最土就這樣了... 我想程式怎麼寫不是重點,重點是algorithm的好壞,因為n by n的matrix當n-->∞時,會做到流眼淚的! 一點點淺見,希望有幫助!