c*****a
发帖数: 808 | 1 careercup看到A家的题
An operation "swap" means removing an element from the array and appending
it at the back of the same array. Find the minimum number of "swaps" needed
to sort that array.
Eg :- 3124
Output: 2 (3124->1243->1234)
How to do it less than O(n^2) ? |
f*********d
发帖数: 140 | |
l*******b
发帖数: 2586 | 3 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
3124 <- 3 在 2前面所以是4-2步
1672345 <- 6在5前面，所以就是 7 - 5 = 2步
1263745 <- 同样也是2步
14325 <- 3在2前面需要5-2 = 3步 |
c*****a
发帖数: 808 | 4
能展开说说吗
【在 f*********d 的大作中提到】
: LIS nlogn
|
f*********m
发帖数: 726 | 5 我想需要的swap数目等于n-LIS吧？
【在 f*********d 的大作中提到】
: LIS nlogn
|
p*****2
发帖数: 21240 | 6 longest increase sequence
2341 需要3步吧
【在 f*********m 的大作中提到】
: 我想需要的swap数目等于n-LIS吧？
|
p*****2
发帖数: 21240 | 7 有说是连续得马
【在 l*******b 的大作中提到】
: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 <- 3 在 2前面所以是4-2步
: 1672345 <- 6在5前面，所以就是 7 - 5 = 2步
: 1263745 <- 同样也是2步
: 14325 <- 3在2前面需要5-2 = 3步
|
p*****2
发帖数: 21240 | 8 require 'set'
def swapsort(arr)
sorted=arr.sort
pos={}
sorted.each_with_index {|num, i| pos[num]=i}
set=Set.new
ret=0
curr=nil
arr.each do |num|
set<
if pos[num]
nil? || num
ret=arr.length-pos[num]-1
curr=num
end
end
ret
end |
l*******b
发帖数: 2586 | 9 算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可
【在 p*****2 的大作中提到】
: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<
|
c*****a
发帖数: 808 | 10
二爷能发个java,c++类吗...
这语言太高级了，有些syntax我跪了
【在 p*****2 的大作中提到】
: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<
|
|
|
p*****2
发帖数: 21240 | 11
你是说哪一段？
【在 l*******b 的大作中提到】
: 算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可
|
p*****2
发帖数: 21240 | 12
就是 luckynoob的算法。但是我做的是数字不连续的。如果连续的就要容易些。
【在 c*****a 的大作中提到】
:
: 二爷能发个java,c++类吗...
: 这语言太高级了，有些syntax我跪了
|
l*******b
发帖数: 2586 | 13 def swapEndSort(a: List[Int]) = {
val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
if(i.isEmpty) 0
else a.length - i.get(0)._2 - 1
}
scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学 |
p*****2
发帖数: 21240 | 14
val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
这句话复杂度多少？
【在 l*******b 的大作中提到】
: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学
|
l*******b
发帖数: 2586 | 15 线性的，照着list一个一个往前找
【在 p*****2 的大作中提到】
:
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: 这句话复杂度多少？
|
s*****1
发帖数: 134 | 16 这题BFS行不行？
3124 有3个adjacent node
1243,3241,3142,
然后再BFS下去，
当然最好还有个hash table,因为可能之前出现过的会再次出现，如果再次出现的话，
Queue就不放进去了 |
c*****a
发帖数: 808 | 17 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
public static int numOfSwap(int[]ar){
List unorder = new ArrayList();
for(int i =0;i
if(i+1ar[i+1])
unorder.add(ar[i]);
}
Collections.sort(unorder);
int biggestUnorder = unorder.get(unorder.size()-1);
if(biggestUnorder > ar[ar.length-1])
return biggestUnorder - ar[ar.length-1];
int smallestUnorder = unorder.get(0);
for(int i = ar.length-1;i>=0;i--){
if(smallestUnorder>ar[i])
return ar[i+1]-ar[i];
}
return -1;
} |
f*********m
发帖数: 726 | 18 哦，我弄错了。
【在 p*****2 的大作中提到】
: longest increase sequence
: 2341 需要3步吧
|
l*******b
发帖数: 2586 | 19 数出来的是不需要动的。一旦动了i+1大小的元素，这个元素就被插到最后了。比它大
的必须都重新插入到最后
【在 c*****a 的大作中提到】
: 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
: public static int numOfSwap(int[]ar){
: List unorder = new ArrayList();
: for(int i =0;i: if(i+1ar[i+1])
: unorder.add(ar[i]);
: }
: Collections.sort(unorder);
: int biggestUnorder = unorder.get(unorder.size()-1);
: if(biggestUnorder > ar[ar.length-1])
|
j*****y
发帖数: 1071 | 20 那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
对了阿。
【在 l*******b 的大作中提到】
: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 <- 3 在 2前面所以是4-2步
: 1672345 <- 6在5前面，所以就是 7 - 5 = 2步
: 1263745 <- 同样也是2步
: 14325 <- 3在2前面需要5-2 = 3步
|
|
|
p*****2
发帖数: 21240 | 21
要找最小的。找到4,3还要继续往下找。
【在 j*****y 的大作中提到】
: 那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
: 对了阿。
|
c********t
发帖数: 5706 | 22 scala确实很酷，感觉以后会一统江湖
【在 l*******b 的大作中提到】
: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学
|
l*******b
发帖数: 2586 | 23 一统江湖估计不行，实用的functional programming总觉得值得学一下，好多概念不太
一样
haskell 总觉得离能用得上比较远，有个xmonad窗口管理器，很有意思。Scala 的包装
和c之类的还挺接近的，可能好学点
【在 c********t 的大作中提到】
: scala确实很酷，感觉以后会一统江湖
|
f*******t
发帖数: 7549 | 24 O(N)解思路是：
（首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
复杂度会升至O(NlogN)，空间额外消耗O(N)）
以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
到后面。所以1的index是几，就要移动几次。
找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
我们就要移几次。
依此类推，扫描一遍数组即能得出答案。
public int minSwap(int[] array) {
if (array == null || array.length < 2)
return 0;
int minSwap = 0;
int target = 1, index = 0;
while (index < array.length) {
if (array[index] == target) {
index++;
target++;
} else {
minSwap++;
index++;
}
}
return minSwap;
} |
w***o
发帖数: 109 | 25 luckynoob的算法是对的。
具体实现可以这样：
1。对原数组排序，不过排序结果是index而不是value，比如：[4，3，2，1]排序后得
到[3，2，1，0]，[2，3，7，4]排序后得到[0，1，3，2]
2。对index数组找到第一个降序元素的index i，比如[3，2，1，0]是1，[0，1，3，2]
是3
3。返回n-i |
l*******b
发帖数: 2586 | 26 nice one!
【在 f*******t 的大作中提到】
: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)
|
b*******e
发帖数: 217 | 27 如果是随便取一堆不重复的数字排序后也可以?
what do you mean """排序后""""也可以做 |
y****n
发帖数: 743 | 28 你的思路是对的，算法是有问题的。
比如：1, 2, 1, 2
只需swap一次，你的算法返回2。
我找到的方法和你的几乎一样，只是需要扫描两遍。
【在 f*******t 的大作中提到】
: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)
|
y****n
发帖数: 743 | 29 这道题如果数组内容是杂乱的有重复依然可以O(N)搞定。
【在 f*******t 的大作中提到】
: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)
|
y****n
发帖数: 743 | 30 思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] < min)
min = arr[i];
}
return swapCount;
} |
|
|
c*****a
发帖数: 808 | 31 careercup看到A家的题
An operation "swap" means removing an element from the array and appending
it at the back of the same array. Find the minimum number of "swaps" needed
to sort that array.
Eg :- 3124
Output: 2 (3124->1243->1234)
How to do it less than O(n^2) ? |
l*******b
发帖数: 2586 | 32 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
3124 <- 3 在 2前面所以是4-2步
1672345 <- 6在5前面，所以就是 7 - 5 = 2步
1263745 <- 同样也是2步
14325 <- 3在2前面需要5-2 = 3步 |
c*****a
发帖数: 808 | 33
能展开说说吗
【在 f*********d 的大作中提到】
: LIS nlogn
|
f*********m
发帖数: 726 | 34 我想需要的swap数目等于n-LIS吧？
【在 f*********d 的大作中提到】
: LIS nlogn
|
p*****2
发帖数: 21240 | 35 longest increase sequence
2341 需要3步吧
【在 f*********m 的大作中提到】
: 我想需要的swap数目等于n-LIS吧？
|
p*****2
发帖数: 21240 | 36 有说是连续得马
【在 l*******b 的大作中提到】
: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 <- 3 在 2前面所以是4-2步
: 1672345 <- 6在5前面，所以就是 7 - 5 = 2步
: 1263745 <- 同样也是2步
: 14325 <- 3在2前面需要5-2 = 3步
|
p*****2
发帖数: 21240 | 37 require 'set'
def swapsort(arr)
sorted=arr.sort
pos={}
sorted.each_with_index {|num, i| pos[num]=i}
set=Set.new
ret=0
curr=nil
arr.each do |num|
set<
if pos[num]
nil? || num
ret=arr.length-pos[num]-1
curr=num
end
end
ret
end |
l*******b
发帖数: 2586 | 38 算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可
【在 p*****2 的大作中提到】
: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<
|
c*****a
发帖数: 808 | 39
二爷能发个java,c++类吗...
这语言太高级了，有些syntax我跪了
【在 p*****2 的大作中提到】
: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<
|
p*****2
发帖数: 21240 | 40
你是说哪一段？
【在 l*******b 的大作中提到】
: 算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可
|
|
|
p*****2
发帖数: 21240 | 41
就是 luckynoob的算法。但是我做的是数字不连续的。如果连续的就要容易些。
【在 c*****a 的大作中提到】
:
: 二爷能发个java,c++类吗...
: 这语言太高级了，有些syntax我跪了
|
l*******b
发帖数: 2586 | 42 def swapEndSort(a: List[Int]) = {
val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
if(i.isEmpty) 0
else a.length - i.get(0)._2 - 1
}
scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学 |
p*****2
发帖数: 21240 | 43
val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
这句话复杂度多少？
【在 l*******b 的大作中提到】
: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学
|
l*******b
发帖数: 2586 | 44 线性的，照着list一个一个往前找
【在 p*****2 的大作中提到】
:
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: 这句话复杂度多少？
|
s*****1
发帖数: 134 | 45 这题BFS行不行？
3124 有3个adjacent node
1243,3241,3142,
然后再BFS下去，
当然最好还有个hash table,因为可能之前出现过的会再次出现，如果再次出现的话，
Queue就不放进去了 |
c*****a
发帖数: 808 | 46 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
public static int numOfSwap(int[]ar){
List unorder = new ArrayList();
for(int i =0;i
if(i+1ar[i+1])
unorder.add(ar[i]);
}
Collections.sort(unorder);
int biggestUnorder = unorder.get(unorder.size()-1);
if(biggestUnorder > ar[ar.length-1])
return biggestUnorder - ar[ar.length-1];
int smallestUnorder = unorder.get(0);
for(int i = ar.length-1;i>=0;i--){
if(smallestUnorder>ar[i])
return ar[i+1]-ar[i];
}
return -1;
} |
f*********m
发帖数: 726 | 47 哦，我弄错了。
【在 p*****2 的大作中提到】
: longest increase sequence
: 2341 需要3步吧
|
l*******b
发帖数: 2586 | 48 数出来的是不需要动的。一旦动了i+1大小的元素，这个元素就被插到最后了。比它大
的必须都重新插入到最后
【在 c*****a 的大作中提到】
: 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
: public static int numOfSwap(int[]ar){
: List unorder = new ArrayList();
: for(int i =0;i: if(i+1ar[i+1])
: unorder.add(ar[i]);
: }
: Collections.sort(unorder);
: int biggestUnorder = unorder.get(unorder.size()-1);
: if(biggestUnorder > ar[ar.length-1])
|
j*****y
发帖数: 1071 | 49 那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
对了阿。
【在 l*******b 的大作中提到】
: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 <- 3 在 2前面所以是4-2步
: 1672345 <- 6在5前面，所以就是 7 - 5 = 2步
: 1263745 <- 同样也是2步
: 14325 <- 3在2前面需要5-2 = 3步
|
p*****2
发帖数: 21240 | 50
要找最小的。找到4,3还要继续往下找。
【在 j*****y 的大作中提到】
: 那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
: 对了阿。
|
|
|
c********t
发帖数: 5706 | 51 scala确实很酷，感觉以后会一统江湖
【在 l*******b 的大作中提到】
: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学
|
l*******b
发帖数: 2586 | 52 一统江湖估计不行，实用的functional programming总觉得值得学一下，好多概念不太
一样
haskell 总觉得离能用得上比较远，有个xmonad窗口管理器，很有意思。Scala 的包装
和c之类的还挺接近的，可能好学点
【在 c********t 的大作中提到】
: scala确实很酷，感觉以后会一统江湖
|
f*******t
发帖数: 7549 | 53 O(N)解思路是：
（首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
复杂度会升至O(NlogN)，空间额外消耗O(N)）
以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
到后面。所以1的index是几，就要移动几次。
找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
我们就要移几次。
依此类推，扫描一遍数组即能得出答案。
public int minSwap(int[] array) {
if (array == null || array.length < 2)
return 0;
int minSwap = 0;
int target = 1, index = 0;
while (index < array.length) {
if (array[index] == target) {
index++;
target++;
} else {
minSwap++;
index++;
}
}
return minSwap;
} |
w***o
发帖数: 109 | 54 luckynoob的算法是对的。
具体实现可以这样：
1。对原数组排序，不过排序结果是index而不是value，比如：[4，3，2，1]排序后得
到[3，2，1，0]，[2，3，7，4]排序后得到[0，1，3，2]
2。对index数组找到第一个降序元素的index i，比如[3，2，1，0]是1，[0，1，3，2]
是3
3。返回n-i |
l*******b
发帖数: 2586 | 55 nice one!
【在 f*******t 的大作中提到】
: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)
|
b*******e
发帖数: 217 | 56 如果是随便取一堆不重复的数字排序后也可以?
what do you mean """排序后""""也可以做 |
y****n
发帖数: 743 | 57 你的思路是对的，算法是有问题的。
比如：1, 2, 1, 2
只需swap一次，你的算法返回2。
我找到的方法和你的几乎一样，只是需要扫描两遍。
【在 f*******t 的大作中提到】
: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)
|
y****n
发帖数: 743 | 58 这道题如果数组内容是杂乱的有重复依然可以O(N)搞定。
【在 f*******t 的大作中提到】
: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)
|
y****n
发帖数: 743 | 59 思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] < min)
min = arr[i];
}
return swapCount;
} |
s******t
发帖数: 229 | 60 那比如 3762514
第一个降序元素的index是5，返回7-5=2
总共换2次就行啦？怎么换啊
2]
【在 w***o 的大作中提到】
: luckynoob的算法是对的。
: 具体实现可以这样：
: 1。对原数组排序，不过排序结果是index而不是value，比如：[4，3，2，1]排序后得
: 到[3，2，1，0]，[2，3，7，4]排序后得到[0，1，3，2]
: 2。对index数组找到第一个降序元素的index i，比如[3，2，1，0]是1，[0，1，3，2]
: 是3
: 3。返回n-i
|
