在2D矩阵中排列数字1

示例2:存在解决方案.rows = {1 3 3}, cols = {2 2 2 1} => COLS = {3/2 1/1}长度2的1个序列递减以满足rows[0] = 1，而长度2的其他2个序列保持长度2.rows[0] = 1COLS = {2/2 1/1 1/1} = {2/2 2/1}长度2的2个序列递减，长度1的1个序列递减.长度已变为0的序列被删除，长度为1的序列被组合.rows[1] = 3COLS = {2/1 1/0 1/1} = {2/1 1/1} = {3/1}可以满足rows[2]的解决方案.rows[2] = 3COLS = {3/0} = {}示例3:解决方案不存在.rows = {0 2 3}, cols = {3 2 0 0} => COLS = {1/3 1/2}rows[0] = 0COLS = {1/3 1/2}rows[1] = 2COLS = {1/2 1/1}rows[2] = 3 => impossible to satisfy; no solution.空间复杂度很容易看到它是O(m + n).时间复杂度我们仅对每一行进行一次迭代.对于每行i，我们最多需要迭代一次COLS的rows[i] <= n个元素.时间复杂度是O(m x n).找到此算法后，我发现以下定理: Havel-Hakimi定理(Havel 1955，Hakimi 1962)指出存在一个矩阵X 为0和1，行总和为a 0 =( a 1 ，a 2 ，…，a n )和列总计b 0 =(b 1 ，b 2 ，…，b m )，使得b i ≥b i + 1 每0<我<当且仅当具有行的0和1的另一个矩阵X n-1，m 总计a 1 =(a 2 ，a 3 ，...，a n )和列总计b 1 =(b 1 −1，b 2 −1，...，b a1 −1，b a1 + 1 ，...，b m )也存在. /p>来自帖子查找二进制矩阵给定行和列之和存在.这基本上是我的算法所做的，同时尝试优化递减部分，即上述定理中的所有 -1 .现在，我看到了上述定理，我知道我的算法是正确的.尽管如此，我还是将其与蛮力算法(最多可容纳50个细胞)进行比较，从而检查了算法的正确性.这是C#实现.public class Pair{ public int Count; public int Length;}public class PairsList{ public LinkedList<Pair> Pairs; public int TotalCount;}class Program{ static void Main(string[] args) { int[] rows = new int[] { 0, 0, 1, 1, 2, 2 }; int[] cols = new int[] { 2, 2, 0 }; bool success = Solve(cols, rows); } static bool Solve(int[] cols, int[] rows) { PairsList pairs = new PairsList() { Pairs = new LinkedList<Pair>(), TotalCount = 0 }; FillAllPairs(pairs, cols); for (int r = 0; r < rows.Length; r++) { if (rows[r] > 0) { if (pairs.TotalCount < rows[r]) return false; if (pairs.Pairs.First != null && pairs.Pairs.First.Value.Length > rows.Length - r) return false; DecrementPairs(pairs, rows[r]); } } return pairs.Pairs.Count == 0 || pairs.Pairs.Count == 1 && pairs.Pairs.First.Value.Length == 0; } static void DecrementPairs(PairsList pairs, int count) { LinkedListNode<Pair> pair = pairs.Pairs.First; while (count > 0 && pair != null) { LinkedListNode<Pair> next = pair.Next; if (pair.Value.Count == count) { pair.Value.Length--; if (pair.Value.Length == 0) { pairs.Pairs.Remove(pair); pairs.TotalCount -= count; } else if (pair.Next != null && pair.Next.Value.Length == pair.Value.Length) { pair.Value.Count += pair.Next.Value.Count; pairs.Pairs.Remove(pair.Next); next = pair; } count = 0; } else if (pair.Value.Count < count) { count -= pair.Value.Count; pair.Value.Length--; if (pair.Value.Length == 0) { pairs.Pairs.Remove(pair); pairs.TotalCount -= pair.Value.Count; } else if(pair.Next != null && pair.Next.Value.Length == pair.Value.Length) { pair.Value.Count += pair.Next.Value.Count; pairs.Pairs.Remove(pair.Next); next = pair; } } else // pair.Value.Count > count { Pair p = new Pair() { Count = count, Length = pair.Value.Length - 1 }; pair.Value.Count -= count; if (p.Length > 0) { if (pair.Next != null && pair.Next.Value.Length == p.Length) pair.Next.Value.Count += p.Count; else pairs.Pairs.AddAfter(pair, p); } else pairs.TotalCount -= count; count = 0; } pair = next; } } static int FillAllPairs(PairsList pairs, int[] cols) { List<Pair> newPairs = new List<Pair>(); int c = 0; while (c < cols.Length && cols[c] > 0) { int k = c++; if (cols[k] > 0) pairs.TotalCount++; while (c < cols.Length && cols[c] == cols[k]) { if (cols[k] > 0) pairs.TotalCount++; c++; } newPairs.Add(new Pair() { Count = c - k, Length = cols[k] }); } LinkedListNode<Pair> pair = pairs.Pairs.First; foreach (Pair p in newPairs) { while (pair != null && p.Length < pair.Value.Length) pair = pair.Next; if (pair == null) { pairs.Pairs.AddLast(p); } else if (p.Length == pair.Value.Length) { pair.Value.Count += p.Count; pair = pair.Next; } else // p.Length > pair.Value.Length { pairs.Pairs.AddBefore(pair, p); } } return c; }}Given the number of rows and columns of a 2d matrixInitially all elements of matrix are 0Given the number of 1's that should be present in each row Given the number of 1's that should be present in each columnDetermine if it is possible to form such matrix.Example: Input: r=3 c=2 (no. of rows and columns)2 1 0 (number of 1's that should be present in each row respectively)1 2 (number of 1's that should be present in each column respectively)Output: Possible Explanation:1 10 10 0I tried solving this problem for like 12 hours by checking if summation of Ri = summation of Ci But I wondered if wouldn't be possible for cases like 3 31 3 00 2 2r and c can be upto 10^5Any ideas how should I move further?Edit: Constraints added and output should only be "possible" or "impossible". The possible matrix need not be displayed. Can anyone help me now? 解决方案 I will illustrate the algorithm with an example.Assume we have m rows and n columns. Let rows[i] be the number of 1s in row i, for 0 <= i < m,and cols[j] be the number of 1s in column j, for 0 <= j < n.For example, for m = 3, and n = 4, we could have: rows = {4 2 3}, cols = {1 3 2 3}, andthe solution array would be: 1 3 2 3 +--------4 | 1 1 1 12 | 0 1 0 13 | 0 1 1 1Because we only want to know whether a solution exists, the values in rows and cols may be permuted in any order. The solution of each permutation is just a permutation of the rows and columns of the above solution.So, given rows and cols, sort cols in decreasing order, and rows in increasing order. For our example, we have cols = {3 3 2 1} and rows = {2 3 4}, and the equivalent problem. 3 3 2 1 +--------2 | 1 1 0 03 | 1 1 1 04 | 1 1 1 1We transform cols into a form that is better suited for the algorithm. What cols tells us is that we have two series of 1s of length 3, one series of 1s of length 2, and one series of 1s of length 1, that are to be distributed among the rows of the array. We rewrite cols to capture just that, that is COLS = {2/3 1/2 1/1}, 2 series of length 3, 1 series of length 2, and 1 series of length 1.Because we have 2 series of length 3, a solution exists only if we can put two 1s in the first row. This is possible because rows[0] = 2. We do not actually put any 1 in the first row, but record the fact that 1s have been placed there by decrementing the length of the series of length 3. So COLS becomes:COLS = {2/2 1/2 1/1}and we combine our two counts for series of length 2, yielding:COLS = {3/2 1/1}We now have the reduced problem:3 | 1 1 1 04 | 1 1 1 1Again we need to place 1s from our series of length 2 to have a solution. Fortunately, rows[1] = 3 and we can do this. We decrement the length of 3/2 and get:COLS = {3/1 1/1} = {4/1}We have the reduced problem:4 | 1 1 1 1Which is solved by 4 series of length 1, just what we have left. If at any step, the series in COLS cannot be used to satisfy a row count, then no solution is possible. The general processing for each row may be stated as follows. For each row r, starting from the first element in COLS, decrement the lengths of as many elements count[k]/length[k] of COLS as needed, so that the sum of the count[k]'s equals rows[r]. Eliminate series of length 0 in COLS and combine series of same length.Note that because elements of COLS are in decreasing order of lengths, the length of the last element decremented is always less than or equal to the next element in COLS (if there is a next element).EXAMPLE 2 : Solution exists.rows = {1 3 3}, cols = {2 2 2 1} => COLS = {3/2 1/1}1 series of length 2 is decremented to satisfy rows[0] = 1, and the 2 other series of length 2 remains at length 2.rows[0] = 1COLS = {2/2 1/1 1/1} = {2/2 2/1}The 2 series of length 2 are decremented, and 1 of the series of length 1.The series whose length has become 0 is deleted, and the series of length 1 are combined.rows[1] = 3COLS = {2/1 1/0 1/1} = {2/1 1/1} = {3/1}A solution exists for rows[2] can be satisfied.rows[2] = 3COLS = {3/0} = {}EXAMPLE 3: Solution does not exists.rows = {0 2 3}, cols = {3 2 0 0} => COLS = {1/3 1/2}rows[0] = 0COLS = {1/3 1/2}rows[1] = 2COLS = {1/2 1/1}rows[2] = 3 => impossible to satisfy; no solution.SPACE COMPLEXITYIt is easy to see that it is O(m + n).TIME COMPLEXITYWe iterate over each row only once. For each row i, we need to iterate over at mostrows[i] <= n elements of COLS. Time complexity is O(m x n).After finding this algorithm, I found the following theorem: The Havel-Hakimi theorem (Havel 1955, Hakimi 1962) states that there exists a matrix Xn,m of 0’s and 1’s with row totals a0=(a1, a2,… , an) and column totals b0=(b1, b2,… , bm) such that bi ≥ bi+1 for every 0 < i < m if and only if another matrix Xn−1,m of 0’s and 1’s with row totals a1=(a2, a3,… , an) and column totals b1=(b1−1, b2−1,… ,ba1−1, ba1+1,… , bm) also exists.from the post Finding if binary matrix exists given the row and column sums.This is basically what my algorithm does, while trying to optimize the decrementing part, i.e., all the -1's in the above theorem. Now that I see the above theorem, I know my algorithm is correct. Nevertheless, I checked the correctness of my algorithm by comparing it with a brute-force algorithm for arrays of up to 50 cells.Here is the C# implementation.public class Pair{ public int Count; public int Length;}public class PairsList{ public LinkedList<Pair> Pairs; public int TotalCount;}class Program{ static void Main(string[] args) { int[] rows = new int[] { 0, 0, 1, 1, 2, 2 }; int[] cols = new int[] { 2, 2, 0 }; bool success = Solve(cols, rows); } static bool Solve(int[] cols, int[] rows) { PairsList pairs = new PairsList() { Pairs = new LinkedList<Pair>(), TotalCount = 0 }; FillAllPairs(pairs, cols); for (int r = 0; r < rows.Length; r++) { if (rows[r] > 0) { if (pairs.TotalCount < rows[r]) return false; if (pairs.Pairs.First != null && pairs.Pairs.First.Value.Length > rows.Length - r) return false; DecrementPairs(pairs, rows[r]); } } return pairs.Pairs.Count == 0 || pairs.Pairs.Count == 1 && pairs.Pairs.First.Value.Length == 0; } static void DecrementPairs(PairsList pairs, int count) { LinkedListNode<Pair> pair = pairs.Pairs.First; while (count > 0 && pair != null) { LinkedListNode<Pair> next = pair.Next; if (pair.Value.Count == count) { pair.Value.Length--; if (pair.Value.Length == 0) { pairs.Pairs.Remove(pair); pairs.TotalCount -= count; } else if (pair.Next != null && pair.Next.Value.Length == pair.Value.Length) { pair.Value.Count += pair.Next.Value.Count; pairs.Pairs.Remove(pair.Next); next = pair; } count = 0; } else if (pair.Value.Count < count) { count -= pair.Value.Count; pair.Value.Length--; if (pair.Value.Length == 0) { pairs.Pairs.Remove(pair); pairs.TotalCount -= pair.Value.Count; } else if(pair.Next != null && pair.Next.Value.Length == pair.Value.Length) { pair.Value.Count += pair.Next.Value.Count; pairs.Pairs.Remove(pair.Next); next = pair; } } else // pair.Value.Count > count { Pair p = new Pair() { Count = count, Length = pair.Value.Length - 1 }; pair.Value.Count -= count; if (p.Length > 0) { if (pair.Next != null && pair.Next.Value.Length == p.Length) pair.Next.Value.Count += p.Count; else pairs.Pairs.AddAfter(pair, p); } else pairs.TotalCount -= count; count = 0; } pair = next; } } static int FillAllPairs(PairsList pairs, int[] cols) { List<Pair> newPairs = new List<Pair>(); int c = 0; while (c < cols.Length && cols[c] > 0) { int k = c++; if (cols[k] > 0) pairs.TotalCount++; while (c < cols.Length && cols[c] == cols[k]) { if (cols[k] > 0) pairs.TotalCount++; c++; } newPairs.Add(new Pair() { Count = c - k, Length = cols[k] }); } LinkedListNode<Pair> pair = pairs.Pairs.First; foreach (Pair p in newPairs) { while (pair != null && p.Length < pair.Value.Length) pair = pair.Next; if (pair == null) { pairs.Pairs.AddLast(p); } else if (p.Length == pair.Value.Length) { pair.Value.Count += p.Count; pair = pair.Next; } else // p.Length > pair.Value.Length { pairs.Pairs.AddBefore(pair, p); } } return c; }} 这篇关于在2D矩阵中排列数字1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！