b***z
发帖数: 921 | 1 两个数列，如［1，2，3，4，5］和［5，3，2，1，4］，求最少要多少次swap能使两个
相同。 |
s*******i
发帖数: 406 | |
u**u
发帖数: 668 | 3 你可以用missing number 的swap algorithm |
b***z
发帖数: 921 | 4 这个算啥难度，我申的DS职位，不是马工。
【在 u**u 的大作中提到】
: 你可以用missing number 的swap algorithm
|
b***z
发帖数: 921 | 5 最少。
【在 s*******i 的大作中提到】
: 最多还是最少？？？？
|
M***6
发帖数: 895 | 6 3次？因为只准swap，不准插入。所以［5，3，2，1，4］里的每个元素最终的位置定下
来了。那么就可以把每个元素的起始位置到最后要到的位置用箭头画出来。这样就可以
看到有两个有向环。总共交换的次数 = 元素的个数 - 环的个数。因为每个环省一次交
换。当两个array完全一样的时候，环的个数等于点数，swap 0次。
这题2，3 构成一个环，5，1，4构成一个环
|-------------
| --- |
| | | |
5 3 2 1 4
| |--|
----------| |
u**u
发帖数: 668 | 7 算hard吧，如果你从来没刷过题，如果不是马工职位
【在 b***z 的大作中提到】
: 这个算啥难度，我申的DS职位，不是马工。
|
l**8
发帖数: 44 | 8 根据uwwu的idea, 和leetcode里missing number的swap algorithm解法：
https://discuss.leetcode.com/topic/22601/swapping-numbers-to-the-same-index-
cell，写了下code. 需要3次swap.
public class Solution {
static int count=0;
public int[] swapNumbers(int[] nums) {
for(int i = 0; i < nums.length; i++)
{
while(i < nums.length && nums[i] == i+1) i++;
while(i < nums.length && nums[i] != i+1)
{
if(nums[i] >nums.length || nums[i] < 1) break;
//swap nums[i] and nums[nums[i]-1]);
nums[i] = nums[i] ^ nums[nums[i]-1] ^ (nums[nums[i]-1] =
nums[i]);
count++;
}
}
return nums;
}
public static void main(String[] args){
int[] nums=new int[]{5,3,2,1,4};
int[] res=new Solution().swapNumbers(nums);
for(int num:res)
System.out.println(num);
System.out.println("Count is "+count);
}
} |
n*****x
发帖数: 686 | 9 不对吧，并没有说数字是1到n，只是要sorted而已
index-
【在 l**8 的大作中提到】
: 根据uwwu的idea, 和leetcode里missing number的swap algorithm解法：
: https://discuss.leetcode.com/topic/22601/swapping-numbers-to-the-same-index-
: cell，写了下code. 需要3次swap.
: public class Solution {
: static int count=0;
: public int[] swapNumbers(int[] nums) {
:
: for(int i = 0; i < nums.length; i++)
: {
: while(i < nums.length && nums[i] == i+1) i++;
|
l**8
发帖数: 44 | |
|
|
d******c
发帖数: 2407 | 11 搜索一下排列和置换，有个专门的记法(a,c,b)之类的，看明白之后就知道算法。跟上
面说的环类似。
许多题都是这样，干想很难，知道现有的理论之后很容易。 |
u**u
发帖数: 668 | |
u**u
发帖数: 668 | 13 在哪里？最近想总结下
【在 d******c 的大作中提到】
: 搜索一下排列和置换，有个专门的记法(a,c,b)之类的，看明白之后就知道算法。跟上
: 面说的环类似。
: 许多题都是这样，干想很难，知道现有的理论之后很容易。
|
l**8
发帖数: 44 | 14 我搜了下，那个概念叫permutation cycle. http://mathworld.wolfram.com/PermutationCycle.html
也叫Cyclic permutation https://en.wikipedia.org/wiki/Cyclic_permutation
这个可以解决Minimum number of swaps needed to change Array 1 to Array 2, as
long as Array1 is a permutation of Array2.
http://stackoverflow.com/questions/2987605/minimum-number-of-swaps-needed-to-change-array-1-to-array-2
就是Mark6说的：总共交换的次数 = 元素的个数 - 环的个数,这里环就是permutation
cycle.
具体实现上，Array1 虽然可以是任何array, 但是我们考虑permutation, 所以可以用1
, 2, 3, …,n表示，相应的Array2就是a permutation of [1,2,..n].
这样问题就可以用missing number的swap algorithm来解了。因为每一次swap，至少一
个数是被放到正确位置的，满足：
Swap two elements with the constraint that either one or both of them should
be swapped into the correct position(s). Until every element is put in its
correct position.
http://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence/15152602#15152602 |
u**u
发帖数: 668 | 15 你挺认真仔细的吗？
知道哪里有好的leetcode各种题型总结吗？
那么多题，其实类型不是很多，我们要举一反10，哈
as
permutation
用1
【在 l**8 的大作中提到】
: 我搜了下，那个概念叫permutation cycle. http://mathworld.wolfram.com/PermutationCycle.html
: 也叫Cyclic permutation https://en.wikipedia.org/wiki/Cyclic_permutation
: 这个可以解决Minimum number of swaps needed to change Array 1 to Array 2, as
: long as Array1 is a permutation of Array2.
: http://stackoverflow.com/questions/2987605/minimum-number-of-swaps-needed-to-change-array-1-to-array-2
: 就是Mark6说的：总共交换的次数 = 元素的个数 - 环的个数,这里环就是permutation
: cycle.
: 具体实现上，Array1 虽然可以是任何array, 但是我们考虑permutation, 所以可以用1
: , 2, 3, …,n表示，相应的Array2就是a permutation of [1,2,..n].
: 这样问题就可以用missing number的swap algorithm来解了。因为每一次swap，至少一
|
l**8
发帖数: 44 | 16 不知道啊。
类型虽然不多，但是能在面试的时候见到题目想到解法，写出代码，比较难。
我也是边刷题，边搜wikipedia， stackoverflow,不懂的就学一学。也看过一点
introduction to algorithms, 但感觉还是要做题，边做边总结。 |
M***6
发帖数: 895 | 17 这样做一道题顶几道。感觉举一反十就是把遇到的题里的知识点弄懂就好了。
【在 l**8 的大作中提到】
: 不知道啊。
: 类型虽然不多，但是能在面试的时候见到题目想到解法，写出代码，比较难。
: 我也是边刷题，边搜wikipedia， stackoverflow,不懂的就学一学。也看过一点
: introduction to algorithms, 但感觉还是要做题，边做边总结。
|
