Вставьте несколько элементов в List или Array (без Linq и не совсем CodeGolf)

Question

Независимо от того, как я пытаюсь, я не могу создать хороший и чистый алгоритм для выполнения следующих действий:

1. System.Array (или универсальный список) data System.Object
2. System.Array (или универсальный список) xval System.Object
3. System.Array (или универсальный список) idxs System.Int32

xval и idxs содержат одинаковое количество элементов, а idxs не содержит значений меньше нуля или большечем data.Length

Мне нужно вставить все элементы в xval в массив data , где соответствующее целое число в idxs представляет индекс вставки в исходных, не поврежденных данных .

Например:

*data* = {A, B, C, D, E, F, G, H}
*xval* = {U, V, W, X, Y, Z}
*idxs* = {5, 0, 0, 0, 1, 1}

*output* = {V, W, X, A, Y, Z, B, C, D, E, U, F, G, H}

Это достаточно легко сделать, но я всегда получаюнеприличный кодМоя лучшая попытка (но я беспокоюсь об ошибках округления):

  idxs.Reverse()
  xval.Reverse()

  Dim N As Int32 = data.Count + xval.Count
  Dim map(N - 1) As Double
  Dim output(N - 1) As Object

  Dim k As Int32 = -1
  For i As Int32 = 0 To data.Count - 1
    k += 1
    map(k) = i
    output(k) = data(i)
  Next
  For i As Int32 = 0 To xval.Count - 1
    k += 1
    map(k) = idxs(i) - ((i + 1) * 1e-8)
    output(k) = xval(i)
  Next

  Array.Sort(map, output)

Answer 1

Вот моя попытка, в которой не используются IndexOf, Sort, Reverse, словари или двойники.

// input data
char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
char[] xval = { 'U', 'V', 'W', 'X', 'Y', 'Z' };
int[] idxs = { 5, 0, 0, 0, 1, 1 };

// algorithm starts here
var output = new List<char>(data);
for (int i = 0; i < idxs.Length; i++)
{
    // Insert the i’th item in the right place
    output.Insert(idxs[i], xval[i]);

    // Increment all the following indexes so that they
    // will insert in the right place
    for (int j = i + 1; j < idxs.Length; j++)
        if (idxs[j] >= idxs[i])
            idxs[j]++;
}

// outputs V, W, X, A, Y, Z, B, C, D, E, U, F, G, H
Console.WriteLine(string.Join(", ", output));

Конечно, если вы не хотите, чтобы алгоритм модифицировал массив idxs, просто сначала сделайте его копию.

Answer 2

'*data* = {A, B, C, D, E, F, G, H}
'*xval* = {U, V, W, X, Y, Z}
'*idxs* = {5, 0, 0, 0, 1, 1}
'*output* = {V, W, X, A, Y, Z, B, C, D, E, U, F, G, H}
    Dim data As New List(Of String)
    Dim xval As New List(Of String)
    Dim idxs As New List(Of Integer)
    Dim output As New List(Of String)

    data.AddRange(New String() {"A", "B", "C", "D", "E", "F", "G", "H"})
    xval.AddRange(New String() {"U", "V", "W", "X", "Y", "Z"})
    idxs.AddRange(New Integer() {5, 0, 0, 0, 1, 1})

    For x As Integer = 0 To data.Count - 1 'for each item in the data
        Dim idx As Integer = idxs.IndexOf(x)
        Do While idx <> -1 'do we have xval's for this index
            output.Add(xval(idx)) 'yes add it
            xval.RemoveAt(idx) 'remove the items from xval
            idxs.RemoveAt(idx) 'and idxs
            idx = idxs.IndexOf(x)
        Loop
        output.Add(data(x)) 'add data item to list
    Next

Answer 3

Я бы пошел на что-то вроде этого (заменить 'char' на 'object')

char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
char[] xval = new char[] { 'U', 'V', 'W', 'X', 'Y', 'Z' };
int[] idxs = new int[] { 5, 0, 0, 0, 1, 1 };
List<char> output = data.ToList();

Dictionary<int, List<char>> dict = new Dictionary<int, List<char>>();
for (int i = 0; i < idxs.Length; i++)
{
    if (!dict.ContainsKey(idxs[i]))
        dict.Add(idxs[i], new List<char>());
    dict[idxs[i]].Add(xval[i]);
}
List<int> keys = dict.Keys.ToList();
keys.Sort();
keys.Reverse();
foreach (int key in keys)
    output.InsertRange(key,dict[key]);

Answer 4

Обратите внимание, что нет инверсии списков.

    IList<Object> data = new Object[] { "A", "B", "C", "D", "E", "F", "G", "H" };
    IList<Object> xval = new Object[] { "U", "V", "W", "X", "Y", "Z" };
    IList<int> idxs = new int[] { 5, 0, 0, 0, 1, 1 };

    List<Object> output = new List<object>(data);

    for (int i = 0; i < xval.Count; i++)
    {
        int currentIndex = idxs[i];
        Object dataElement= data[currentIndex]; // We should insert the new element before this element.
        int elementsIndex = output.IndexOf(dataElement);
        output.Insert(elementsIndex, xval[i]);
    }
    return output;