矩阵的转置，空间复杂度O(1)

超、凢脫俗 2024-04-18 18:26 38阅读 0赞

原矩阵: 
    一维存放格式 int nums[] = {0,1,2,3,4,5,6,7,8,9,10,11}
    行数：3
    列数：4
    0 1 2 3 
    4 5 6 7
    8 9 10 11
    
    转置后
    
    0 4 8
    1 5 9
    2 6 10
    3 7 11
    索引变化
    0 -> 0
    1 -> 3
    2 -> 6
    3 -> 9
    4 -> 1
    5 -> 4
    6 -> 7
    7 -> 10
    8 -> 2
    9 -> 5
    10 -> 8
    11 -> 11
    构成环：
    0 -> 0
    11 -> 11
    1 -> 3 -> 9 -> 5 -> 4 -> 1
    2 -> 6 -> 7 -> 10 -> 8 -> 2
    所以我们要解决环的问题
    
    m*n 的矩阵，转置为 n*m的矩阵
    转之前，第 i 个元素在矩阵中的坐标为 (i/m, i%m)
    所以转置后坐标变为 (i%m, i/m)

//  找到当前元素前一个元素的索引位置
    int preIdx(int idx, int rows, int cols)
    {
        return (idx % rows) * cols + (idx / rows);
    }
    
    //  找到当前元素后一个元素的索引位置
    int nextIdx(int idx, int rows, int cols)
    {
        return (idx % cols) * rows + (idx / cols);
    }
    
    //  处理环
    void move(int *nums, int idx, int rows, int cols)
    {
        int currentVal = nums[idx];
        int current = idx;  // 当前需要移动位置的索引位置
        int pre = preIdx(idx, rows, cols);    //先记录当前元素的前一个元素索引
        while (idx != pre)  //如果移动后元素的前一个索引不与环的起始索引相等，继续移动元素
        {
            nums[current] = nums[pre];  //把转换前的的园所和转换后的元素进行位置交换
            current = pre;  
            pre = preIdx(current, rows, cols);
        }
        nums[current] = currentVal;
    }
    
    void transpose(int *nums, int rows, int cols)
    {
        for (int i = 0; i < rows * cols; i++)
        {
            int next = nextIdx(i, rows , cols);
            while (i < next)    // 如果next > i 说明环已经处理过
            {
                next = nextIdx(next, rows, cols);
            }
            if (next == i)
            {
                move(nums, i, rows, cols);
            }
        }
    }
    
    void printNums(int *nums, int rows, int cols)
    {
        for (int i = 0; i < rows * cols; i++)
        {
            printf("%d ",nums[i]);
            if ((i + 1) % cols == 0)
            {
                printf("\n");
            }   
        }
    }
    int main()
    {
    
        int nums[12] = {1,2,3,4,5,6,7,8,9,10,11,12};
        printNums(nums, 3, 4);
        transpose(nums, 3, 4);
        printNums(nums, 4, 3);
        return 0;
    }