在c#中旋转列表的最简单方法

Question

列表说我有一个清单 List<int> {1,2,3,4,5}

旋转意味着:

=> {2,3,4,5,1} => {3,4,5,1,2} => {4,5,1,2,3}

也许旋转不是最好的词,但希望你明白我的意思

我的问题,最简单的方法(简短的代码,c#4 Linq准备好),并且不会受到性能的影响(合理的性能)

谢谢.

Answer 1

List<T>

在最简单的方法(一List<T>)是使用:

int first = list[0];
list.RemoveAt(0);
list.Add(first);

虽然表现令人讨厌 - O(n).

排列

这基本上等同于List<T>版本,但更多手册:

int first = array[0];
Array.Copy(array, 1, array, 0, array.Length - 1);
array[array.Length - 1] = first;

LinkedList<T>

如果你可以使用LinkedList<T>,那会更简单:

int first = linkedList.First;
linkedList.RemoveFirst();
linkedList.AddLast(first);

这是O(1),因为每个操作都是恒定时间.

Queue<T>

cadrell0使用队列的解决方案是单个语句,因为Dequeue删除元素并返回它:

queue.Enqueue(queue.Dequeue());

虽然我不能找到的这个性能特性的任何文档,我期望 Queue<T>使用阵列和索引为"虚拟起点"来实现-在这种情况下,这是另一种O(1)的解决方案.

请注意,在所有这些情况下,您都要先检查列表是否为空.(你可能认为这是一个错误,或者是一个无操作.)

Answer 2

您可以将其实现为队列.将相同的值排队并排队.

**我不确定将List转换为队列的性能,但是人们对我的评论提出了赞成,所以我将其作为答案发布.

Answer 3

我用这个:

public static List<T> Rotate<T>(this List<T> list, int offset)
{
    return list.Skip(offset).Concat(list.Take(offset)).ToList();
}

Answer 4

似乎有些回答者将此视为探索数据结构的机会.虽然这些答案内容丰富且有用,但它们并不是非常Linq'ish.

Linq'ish方法是:你得到一个扩展方法,它返回一个懒惰的IEnumerable,知道如何构建你想要的东西.此方法不会修改源,只应在必要时分配源的副本.

public static IEnumerable<IEnumerable<T>> Rotate<T>(this List<T> source)
{
  for(int i = 0; i < source.Length; i++)
  {
    yield return source.TakeFrom(i).Concat(source.TakeUntil(i));
  }
}

  //similar to list.Skip(i-1), but using list's indexer access to reduce iterations
public static IEnumerable<T> TakeFrom<T>(this List<T> source, int index)
{
  for(int i = index; i < source.Length; i++)
  {
    yield return source[i];
  }
}

  //similar to list.Take(i), but using list's indexer access to reduce iterations    
public static IEnumerable<T> TakeUntil<T>(this List<T> source, int index)
{
  for(int i = 0; i < index; i++)
  {
    yield return source[i];
  }
}

用作:

List<int> myList = new List<int>(){1, 2, 3, 4, 5};
foreach(IEnumerable<int> rotation in myList.Rotate())
{
  //do something with that rotation
}