不同的初始矩阵

-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

谢谢澄清@丹尼尔。顺利实施。 :) –

不同的初始矩阵

回答

相关问题