如何查找数组中重新排列的元素数 [英] How to find the number of rearranged elements in array

问题描述

我有一个列表，如下所示:

I have a List as follows:

{1, 7, 4, 9, 5}

我需要一个排序列表作为{1, 4, 5, 7, 9}

我想找到交换以获得此排序列表的元素数.

I want to find the number of elements swapped to get this sorted list.

第一步后:{1, 4, 7, 9, 5}

第二次移动后:{1, 4, 5, 7, 9}

答案为: 2 移动

哪种方法最合适? 有没有办法使用 Linq ?

Which is the optimum way to do it? Using Linq is there a way?

推荐答案

好吧，如果我没错理解 ，那么您要计算删除/插入:

Well, if I've understood you right you want to count deletions / insertions:

1. 将7放在第四位，
2. 采用9并排在第五位，
3. 将5放在3d位置

1. Take 7 and put it on 4th place,
2. Take 9 and put it on 5th place,
3. Take 5 and put it on 3d place

我们有{1, 4, 5, 7, 9}，该{1, 4, 5, 7, 9}通过3操作进行了排序.如果是您的情况，可以

we have {1, 4, 5, 7, 9} which is sorted with 3 operations. If' it's your case you can

对列表进行排序:

 {1, 7, 4, 9, 5}  # initial
  |  |  |  |  |
 {1, 4, 5, 7, 9}  # sorted

现在建立无序图:

• 节点:数字(1，7，...，5)
• 边:每列(初始列表和排序列表)中的数字之间:1 - 1，7 - 4，4 - 5，9 - 7，5 - 9

• nodes: numbers (1, 7, ..., 5)
• edges: between numbers in each column (initial and sorted list): 1 - 1, 7 - 4, 4 - 5, 9 - 7, 5 - 9

找出所有循环:

1 - 1          # length == 1
7 - 4 - 5 - 9  # length == 4

对所有循环的所有length - 1求和:

Sum all the length - 1 of all loops:

(1 - 1) + (4 - 1) = 3

:如果插入的是 (请注意，我们不交换个项目)，答案是

In case of insertions (please, note that we don't swap items) only the answer is

|List| - |Longest_Non_Descreasing_Sequence(List)|

|...|代表项数(Count，Length，Size等).就您而言:

were |...| stands for number of items (Count, Length, Size etc). In your case:

|{1, 7, 4, 9, 5}| = 5
|Longest_Non_Descreasing_Sequence({1, 7, 4, 9, 5})| = |{1, 4, 5}| = 3

 result = 5 - 3 = 2

算法:

1. 借助动态编程，找出最长的非降序序列(LNDS)
2. 将其余项目插入其中.

对于您来说，对于{1, 7, 4, 9, 5}，对于LNDS，我们有{1, 4, 5}；还有两个要插入的{7, 9}:

In your case for {1, 7, 4, 9, 5} we have {1, 4, 5} for LNDS and two items {7, 9} to insert:

 {1, 7, 4, 9, 5} # initial List {1, 4, 5} is LNDS
 {1, 4, 9, 5, 7} # 7 inserted into {1, 4, 5} we have {1, 4, 5, 7} as LNDS
 {1, 4, 5, 7, 9} # 9 inserted into {1, 4, 5, 7}

这篇关于如何查找数组中重新排列的元素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！