由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问道面试题
相关主题
新鲜C3 energy面经找2个sorted array中的第K小的元素,有O(lgn)方法吗?
问题:Find the minimum number of "swaps" needed to sort an arrayNon-recursive permutation
一个容易记忆的permutation算法两个Sorted Array,找K smallest element
问个google面试题问一下deep copy和shallow copy的问题(C#)
一道面试题Find the intersection of two sorted arrays【扩展】
问一道g电面题Given a string, find all its permutations without any repetition?
被Facebook的面试的一道题目难倒了请教一下external sorting的问题
老问题了,网上竟然找不到答案a question
相关话题的讨论汇总
话题: nums话题: swap话题: int话题: array
进入JobHunting版参与讨论
1 (共1页)
b***z
发帖数: 921
1
两个数列,如[1,2,3,4,5]和[5,3,2,1,4],求最少要多少次swap能使两个
相同。
s*******i
发帖数: 406
2
最多还是最少????
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
10
如果最终的array只是一个sorted array, 用sorted array using swap?
http://stackoverflow.com/questions/39033882/sorted-array-in-java-using-swap-methods
怎么确保swap数最少?
相关主题
问一道g电面题找2个sorted array中的第K小的元素,有O(lgn)方法吗?
被Facebook的面试的一道题目难倒了Non-recursive permutation
老问题了,网上竟然找不到答案两个Sorted Array,找K smallest element
进入JobHunting版参与讨论
d******c
发帖数: 2407
11
搜索一下排列和置换,有个专门的记法(a,c,b)之类的,看明白之后就知道算法。跟上
面说的环类似。
许多题都是这样,干想很难,知道现有的理论之后很容易。
u**u
发帖数: 668
12
http://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence/15152602#15152602
看看思想 就大概知道证明了

【在 l**8 的大作中提到】
: 如果最终的array只是一个sorted array, 用sorted array using swap?
: http://stackoverflow.com/questions/39033882/sorted-array-in-java-using-swap-methods
: 怎么确保swap数最少?

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, 但感觉还是要做题,边做边总结。

1 (共1页)
进入JobHunting版参与讨论
相关主题
a question一道面试题
再论 mini # of swaps to sort array.问一道g电面题
minMSwap 这题能比O(n^2)更快的解法吗被Facebook的面试的一道题目难倒了
问一问这个题。老问题了,网上竟然找不到答案
新鲜C3 energy面经找2个sorted array中的第K小的元素,有O(lgn)方法吗?
问题:Find the minimum number of "swaps" needed to sort an arrayNon-recursive permutation
一个容易记忆的permutation算法两个Sorted Array,找K smallest element
问个google面试题问一下deep copy和shallow copy的问题(C#)
相关话题的讨论汇总
话题: nums话题: swap话题: int话题: array