C#陣列元素移動/交換 (Array Shift)

2020-03-19

1638
0
2020-03-20

同樣是CodeFight時遇到的情境

題目出處 Arcade > Thr Core > 109 Contours Shifting

給定一個長方形的Array int[][] matrix，將matrix由外至內分為多個圈

第0圈的所有元素順時針移動一個位置；第1圈的所有元素逆時針移動一個位置...for 第i圈(0-base)，i為偶數則順時針移動，反之逆時針移動

回傳將matrix所有圈依照此規則移動後的結果

ex:
matrix = [[ 1,  2,  3,  4],
          [ 5,  6,  7,  8],
          [ 9, 10, 11, 12],
          [13, 14, 15, 16],
          [17, 18, 19, 20]]

第0圈為 1, 2, 3, 4, 8, 12, 16, 20, 19, 18, 17, 13, 9, 5
第1圈為 6, 7, 11, 15, 14, 10

移動完畢後得到
contoursShifting(matrix) = [[ 5,  1,  2,  3],
                            [ 9,  7, 11,  4],
                            [13,  6, 15,  8],
                            [17, 10, 14, 12],
                            [18, 19, 20, 16]]

n × 1 array ，旋轉中心在其左方
[[238],     [[245],
 [239],      [238],
 [240],      [239],
 [241],  =>  [240],
 [242],      [241],
 [243],      [242],
 [244],      [243],
 [245]]      [244]]


1 × n array ，旋轉中心在其下方
[[238,239,240,241,242,243,244,245]] => [[245,238,239,240,241,242,243,244]]

示意圖

如果以順時針方向抽取出第0圈的元素放在一個array中，順時針移動相當於將其做了一個頭尾相接的右移後放回原本位置；反之亦然。這裡就先實現了這個概念的code

// 頭尾相接的右移
IEnumerable<T> ShiftRightCyclic<T>(IEnumerable<T> s, int shifts)
{
    int cnt = s.Count();
    shifts %= cnt;
    var last = s.Where((x,idx) => cnt - idx <= shifts);
    return last.Concat(s).Take(cnt);
}
// 頭尾相接的左移
IEnumerable<T> ShiftLeftCyclic<T>(IEnumerable<T> s, int shifts)
{
    int cnt = s.Count();
    shifts %= cnt;
    var first = s.Take(shifts);
    return s.Skip(shifts).Concat(first);
}

可以用一個簡單的範例看一下效果

接著就是要抽取出matrix中的圈，並將其移動後重新放回去就完成了

int[][] contoursShifting(int[][] matrix) {
    // 由外至內一圈一圈處理
    for(int r=0; r<=(Math.Min(matrix.Length, matrix[0].Length)-1)/2; r++)
    {
        // 這邊先定義出該圈的index範圍
        int jStart = r, iStart = r, jEnd = matrix[0].Length-1-r, iEnd = matrix.Length-1-r;
        var jRange = Enumerable.Range(jStart, jEnd-jStart+1);
        var iRange = Enumerable.Range(iStart, iEnd-iStart+1);

        // 這邊取出各邊界的index，以上>右>下>左順序組出該圈的index
        // index以Tuple<int,int>表示
        var tIdx = jRange.Select(x => (i:iStart, j:x));             // top
        var rIdx = iRange.Select(x => (i:x, j:jEnd));               // right
        var bIdx = jRange.Reverse().Select(x => (i:iEnd, j:x));     // bottom
        var lIdx = iRange.Reverse().Select(x => (i:x, j:jStart));   // left
        var ringIdx = tIdx.Concat(rIdx).Concat(bIdx).Concat(lIdx).Distinct().ToArray();

        // 以圈的index取得圈的值
        var oriVal = ringIdx.Select(x => matrix[x.i][x.j]);

        // 執行左移或右移
        var newVal = r%2 == 0 ? ShiftRightCyclic(oriVal, 1).ToArray() : ShiftLeftCyclic(oriVal, 1).ToArray();
        
        // 將移動後的結果透過圈的index寫回matrix
        for(int i=0; i<ringIdx.Length; i++)
        {
            var loc = ringIdx[i];
            matrix[loc.i][loc.j] = newVal[i];
        }
    }
    return matrix;
}

過程中可以加上Dump查看index與value狀況

我在100 Reverse On Diagonals、101 Swap Diagonals、104 Volleyball Positions、105 Star Rotation等題也使用了類似概念處理元素的移動/交換，感覺上相對容易理解一些

參考:

https://codesignal.com/

回首頁