Given a square matrix of integers m, your task is to rearrange its numbers in the following way:
- First, sort its values in ascending order of how frequently the number occurs in m. In the case of a tie, sort the equally frequent numbers by their values, in ascending order.
- Second, place the sorted numbers diagonally, starting from the bottom right corner, like this:
This is my idea
def sortMatrixByOccurrences(m):
import heapq
from collections import defaultdict
hasht = defaultdict(int)
# count occurences of each num in matrix
for row in range(m):
for col in range(m):
hasht[m[row][col]] += 1
# push onto heap first by # occurs, then by desc digit
heap = []
for key, val in hasht.items():
heapq.heappush(heap, (-val,key))
# traverse matrix's diags towards bottom left
# the start of each diag traversal is the top row, then last col
for diag_head in (m+m-1):
row = 0 if diag_head < m else diag_head - m + 1
col = diag_head if diag_head < m else m-1
occurs, dig = heapq.heappop()[1]
for _ in range(occurs):
matrix[row][col] = dig
I think this is O(mlogm) Time with the heappushes being the longest operation, O(m*m) space for the heap and hashtable?
Comments (3)