c++ - 如何在 C++ 中重新定位一个数组中的元素

Question

我参加了这个面试问题，但我失败了，所以我来这里是为了不再失败！

我有一个大小为 16 且 5 < givenIndex < 10 的 int 数组。

我必须将此索引中的元素打印为每个可能的数组（有 16 个），方法是将 givenIndex 处的元素移动到数组中的每个位置并推动其余元素。

例如：

int array[16] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
int givenIndex = 6;

因为array[givenIndex] = 7，我需要将 7 移动到每个可能的位置并打印该数组。

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

[7,1,2,3,4,5,6,8,9,10,11,12,13,14,15,16]

[1,7,2,3,4,5,6,8,9,10,11,12,13,14,15,16]

[1,2,7,3,4,5,6,8,9,10,11,12,13,14,15,16]

这是16个案例。

我正在尝试的是：

for(int i = 0;i<16;i++){
        array[i] = array[indexInsercion]
        if (i<indexInsert){
            //right shift
            array[i] = array[i+1]
        }else if(i == indexInsert){
            //no shift
        }else{
            //left shift
            array[i] = array[i-1]
        }
    }

我能得到一些帮助吗？

Answer 1

我们只能猜测面试官希望看到什么。如果我是面试官，我希望你能保持简单。这是我认为可以期望在面试情况下从头开始编写的代码：

#include <iostream>
#include <array>

template <size_t size>
void print_replaced(const std::array<int,size>& x,size_t index){
    for (int i=0;i<size;++i){
        for (int j=0;j<i;++j) {
            if (j == index) continue;
            std::cout << x[j] << " ";
        } 
        std::cout << x[index] << " ";
        for (int j=i;j<size;++j) {
            if (j == index) continue; 
            std::cout << x[j] << " ";
        }
        std::cout << "\n";
    }
}


int main() {
    std::array<int,16> x{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    print_replaced(x,6);
}

这是解决问题的第一种方法，循环打印 16 种不同的数组元素组合。打印每一行遵循简单的逻辑：我们打印应该替换的元素之前的所有元素，然后是应该洗牌的元素，然后是剩余的元素。

这很简单，但却是错误的。它的输出是：

7 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 
1 7 2 3 4 5 6 8 9 10 11 12 13 14 15 16 
1 2 7 3 4 5 6 8 9 10 11 12 13 14 15 16 
1 2 3 7 4 5 6 8 9 10 11 12 13 14 15 16 
1 2 3 4 7 5 6 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 7 6 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 8 7 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 8 9 7 10 11 12 13 14 15 16 
1 2 3 4 5 6 8 9 10 7 11 12 13 14 15 16 
1 2 3 4 5 6 8 9 10 11 7 12 13 14 15 16 
1 2 3 4 5 6 8 9 10 11 12 7 13 14 15 16 
1 2 3 4 5 6 8 9 10 11 12 13 7 14 15 16 
1 2 3 4 5 6 8 9 10 11 12 13 14 7 15 16 
1 2 3 4 5 6 8 9 10 11 12 13 14 15 7 16 

有一行出现两次，最后一行丢失。

作为一名面试官，我不会对第一次尝试没有产生正确的输出感到惊讶。我不在乎那个。那不是减号。我关心的是你对此有何反应。你知道接下来的步骤吗？你有修复错误输出的策略吗？还是您只是因为第一次尝试没有设法编写正确的代码而感到恐慌？这就是我想在面试中检查的内容，然后这就是练习的结束。我想问更多不同的问题，而不是给你时间来修复所有错误并编写正确的经过良好测试的代码，因为我知道这比我们在面试中花费的时间更多。

我会把它留给你来修复上面的代码；）

Answer 2

这是一个快速的尝试。基本上只需跟踪给定索引应该去哪里并在那里打印它以及跳过它所在的原始位置。

#include <iostream>

int main()
{
    int array[16] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
    int givenIndex = 6;

    for (int p = 0; p <= 16; ++p)
    {
        if (p != givenIndex)
        {
            std::cout << "[";
            for (int i = 0; i < 16; ++i)
            {
                if (i == p)
                {
                    if (i > 0)
                    {
                        std::cout << ",";
                    }
                    std::cout << array[givenIndex];
                }
                if (array[i] != array[givenIndex])
                {
                    if (i > 0 || p == 0)
                    {
                        std::cout << ",";
                    }
                    std::cout << array[i];
                }
            }
            if (p == 16)
            {
                std::cout << "," << array[givenIndex];
            }
            std::cout << "]\n";
        }
    }
}

输出：

[7,1,2,3,4,5,6,8,9,10,11,12,13,14,15,16]
[1,7,2,3,4,5,6,8,9,10,11,12,13,14,15,16]
[1,2,7,3,4,5,6,8,9,10,11,12,13,14,15,16]
[1,2,3,7,4,5,6,8,9,10,11,12,13,14,15,16]
[1,2,3,4,7,5,6,8,9,10,11,12,13,14,15,16]
[1,2,3,4,5,7,6,8,9,10,11,12,13,14,15,16]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
[1,2,3,4,5,6,8,7,9,10,11,12,13,14,15,16]
[1,2,3,4,5,6,8,9,7,10,11,12,13,14,15,16]
[1,2,3,4,5,6,8,9,10,7,11,12,13,14,15,16]
[1,2,3,4,5,6,8,9,10,11,7,12,13,14,15,16]
[1,2,3,4,5,6,8,9,10,11,12,7,13,14,15,16]
[1,2,3,4,5,6,8,9,10,11,12,13,7,14,15,16]
[1,2,3,4,5,6,8,9,10,11,12,13,14,7,15,16]
[1,2,3,4,5,6,8,9,10,11,12,13,14,15,7,16]
[1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,7]

Answer 3

如果期望只是按给定顺序打印数组的元素：

跟踪要打印的数组元素的当前索引，例如indx-

• 如果当前元素处理的位置等于行号，则在 处打印元素givenIndex。
• 如果indx等于givenIndex跳过它并打印indx + 1元素，否则打印元素并indx增加indx。1

执行：

#include <iostream>
#include <array>

int main() {
    std::array<int, 16> array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    std::size_t givenIndex = 6;

    for (std::size_t i = 0, indx = 0; i < array.size(); indx = 0, ++i) {
        std::cout << '[';

        for (std::size_t j = 0; j < array.size(); ++j) {
            if (j == i) {
                std::cout << array[givenIndex] << ',';
                continue;
            }

            if (indx == givenIndex) {
                ++indx;
            }

            std::cout << array[indx++] << ',';
        }

        std::cout << ']';
        std::cout << '\n';
    }

    return 0;
}

输出：

# ./a.out
[7,1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,7,2,3,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,7,3,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,7,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,7,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,7,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,7,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,7,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,7,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,7,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,7,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,7,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,14,7,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,14,15,7,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,7,]

如果期望改变数组中元素的顺序，然后打印数组：

首先将元素移动givenIndex到数组的0^{第 th}索引，然后 -

• 打印数组
• 在每次迭代中，将当前元素与数组中的下一个元素交换并打印。

执行：

#include <iostream>
#include <array>

void print_array (std::array<int, 16>& array) {
    std::cout << '[';
    for (std::size_t indx = 0; indx < array.size(); ++indx) {
        std::cout << array[indx] << ',';
    }
    std::cout << ']';
    std::cout << '\n';
}

void rearrange_array_elem (std::array<int, 16>& array, std::size_t givenIndx) {
    // move the element at givneIndx to first position in array
    for (std::size_t j = givenIndx; j > 0; --j) {
        std::swap (array[j], array[j - 1]);
    }

    // print array
    print_array (array);

    for (std::size_t indx = 0; indx < array.size() - 1; ++indx) {
        // swap current element with its next element
        std::swap (array[indx], array[indx + 1]);
        print_array (array);
    }
}

int main() {
    std::array<int, 16> array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    std::size_t givenIndex = 6;

    rearrange_array_elem (array, givenIndex);

    return 0;
}

输出：

# ./a.out
[7,1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,7,2,3,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,7,3,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,7,4,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,7,5,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,7,6,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,7,9,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,7,10,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,7,11,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,7,12,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,7,13,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,7,14,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,14,7,15,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,14,15,7,16,]
[1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,7,]