不同的初始矩陣

-1

對於從1到A * B的所有不同數字的A * B矩陣，我們首先對每列進行排序，然後按指數遞增順序連接所有列，以形成大小爲A * B的數組。按從左到右的順序依次編號。不同的初始矩陣

例如，如果基質是

[1 5 6] [3 2 4]

我們首先排序的所有列以獲得

[1 2 4] [3 5 6 ]

現在，我們串聯列中增加索引的次序來獲得的數組

[1,3，2,5，4,6]

給出這個最終數組，你必須計算有多少不同的初始矩陣是可能的。以10^9 + 7模數返回所需的答案。

兩個矩陣是不同的，如果： - 它們的尺寸不同。 - 或者如果兩個矩陣中的相應行有任何不同。

實施例：

如果輸入數組是[1,3，2，4]，可能的不同初始矩陣是：

[1 3 2 4]

====== ======

[1 2]

[3 4]

=============

[1 4]

[3 2]

===========

[3 2]

[1 4]

===========

[3 4]

[1 2]

===========

即，總共5點矩陣。

這是做了什麼：我找到了我們可以在每個大小的子數組（len/2）中排列值的方法。因此，如果一個數組[1,2,3,4] 我們有兩個子數組[1,2] & [3,4]。所以答案將是2！* 2！.Thing是我們必須得到的獨特的行也是如此。那就是我的代碼失敗的地方。你能否在正確的方向給我啓發。這是我的代碼;

public int cntMatrix(ArrayList<Integer> a) { 
    if(a.size()==1){ 
     return 1; 
    } 

    int n=a.size(); 
    int len=n/2; 
    int i=0; 
    long ans=1; 
    if(n%2!=0){ //n is odd 

     ans=fact(n); //factorial function 

    }else{ 

    while(i<n){ 

     int x=i; 
     int y=i+len; 

     HashMap<Integer,Integer> map=new HashMap<>(); //frequency of each element in subarray[x..y] 

     for(int m=i;m<y;m++){ 

      if(map.containsKey(a.get(m))){ 
       map.put(a.get(m),map.get(a.get(m))+1); 
      }else{ 
       map.put(a.get(m),1); 
      } 
     } 

     long p=fact(len); 
     long q=1; 
    for(Map.Entry<Integer,Integer> set:map.entrySet()){ 
      int key=set.getKey(); 
      int value=set.getValue(); 
      q*=fact(value); 
     } 

     ans*=p/q; //ncr 

     map.clear(); 
     i+=len; 
    } 
    } 
    ans%=1000000007; 
    return ((int)ans+1); 
}

如何應對唯一的行

詢及interviewbit.com

來源

2017-08-13 Akash_Triv3di

好的，但既不是電腦也不知道你是如何失敗，除非你顯示你的代碼 – emotionlessbananas

@I_Am_Innocent：對不起。我在這裏是新的，沒有注意到代碼不在那裏。總是愉快地編輯。 –

有一兩件事我注意到的是，你檢查的長度是奇數還是不行。

這是不對的，例如，如果長度是9，你可以安排一個3x3的矩陣來滿足條件。

我認爲你應該嘗試將數組「切」成大小爲1-n的列，並且對於每個大小檢查它是否可以是初始矩陣。我的算法的複雜性是O（n^2），儘管我覺得有更好的一個。

這是我的Python代碼 -

class Solution: 
# @param A : list of integers 
# @return an integer 
def cntMatrix(self, A): 
    count = 0 
    n = len(A) 
    # i = number of rows 
    for i in range(1, n + 1): 
     if n % i == 0: 
      can_cut = True 
      start = 0 
      while start < len(A) and can_cut: 
       prev = 0 
       for j in range(start, start + i): 
        if prev > A[j]: 
         can_cut = False 
        prev = A[j] 
       start += i 

      if can_cut: 
       count = (count + pow(math.factorial(i), n/i)) % (pow(10, 9) + 7) 

    return count

我沒有檢查他們的網站上，因爲這個問題頁面無法找到了，我看到了它只能在忍者測試。

運行後 -

s = Solution() 
print(s.cntMatrix([1, 2, 3, 1, 2, 3, 1, 2, 3]))

我們得到 - 217 = 3！ * 3！ * 3！ + 1

來源

2017-08-26 09:21:40

謝謝澄清@丹尼爾。順利實施。 :) –

不同的初始矩陣

回答

相關問題