|
锁定老帖子 主题：最大公约数的应用 - 分享
精华帖 (1) :: 良好帖 (2) :: 新手帖 (15) :: 隐藏帖 (10)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-06-28
qiyueguxing 写道 我很想知道楼上几位哥们从事的职业和行业
我猜测：1.你们是在校研究生 2.你们还未出大学校门 ---------------- Java工程师- 喜欢很基础的东西 |
| 返回顶楼 | |
|
发表时间：2010-06-28
tanlingcau 写道 maozj 写道 1.2 算法2： (1) 问题分析： 在算法有空间限制的情况下，一个简单的方法是： 将最后一个存储空间的数据存储在临时存储空间中。 其余数逐个向后移动一位。共操作k次就能完成问题的要求。 (2) 代码： package boke.written;
import java.util.Arrays;
/**
* 题目：数组中有n个数据，要将它们顺序循环向后移动k位，即前面的元素向后移动k位，后面的元素则循环
* 向前移k位，例如，0、1、2、3、4循环移动3位后为2、3、4、0、1。考虑到n会很大，不允许用2n以上 个空间来完成此题。
*
* @since jdk1.5及其以上
* @author 毛正吉
* @version 1.0
* @date 2010.06.20
*
*/
public class GCDTest2 {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 0, 1, 2, 3, 4 };
int n = a.length;
int k = 3;
int temp;
int j;
for (int i = 0; i 0; j--) { // 其余数据逐个向后移动一位
a[j] = a[j - 1];
}
a[0] = temp;
}
System.out.println(Arrays.toString(a));
}
}
(3) 算法分析： 若要考虑到有k>n的可能性，这样的移动会出现重复操作，可以在输入数据后，执行k = k % n操作，可以保证不出现重复移动的情况。这时算法的移动(赋值)次数为k * n，当n较大时，算法的效率比较低。 时间复杂度为O(n * k), 空间效率为O(n). 把最后k在放到temp中，一次移动k位。 ------------------------------- 你的结论是错的 |
| 返回顶楼 | |
|
发表时间：2010-06-28
bryande 写道 楼主算法设计的不好
可以参考楼上的 时间复杂度为O(n),空间复杂度为O(1) ---------------- 楼上的结论是错的 |
| 返回顶楼 | |
|
发表时间：2010-06-30
我写了个算法，很简单：找每个元素的正确位置，然后放进去，用递归的。
复制度为O(n)
import static org.junit.Assert.assertTrue;
import java.util.Arrays;
import org.junit.Test;
public class MoveTest {
public void doMove(int a[], int k, int c, int v, int i) {
int n = a.length;
if (i < n) {
int j = (c + k) % n;
int tmp = a[j];
a[j] = v;
doMove(a, k, j, tmp, ++i);
}
}
public void move(int a[], int k) {
assert null != a;
assert 0 < k;
int n = a.length;
int r = k % n;
if (1 > n || 0 == r) {
return;
}
doMove(a, k, 0, a[0], 0);
}
@Test
public void testMove0() {
int a[] = {23, 5, 24, 15, 30};
int k = 1;
int e1[] = {30, 23, 5, 24, 15};
move(a, k);
assertTrue(Arrays.equals(a, e1));
k = 2;
int e2[] = {24, 15, 30, 23, 5};
move(a, k);
assertTrue(Arrays.equals(a, e2));
k = 3;
int e3[] = {30, 23, 5, 24, 15};
move(a, k);
assertTrue(Arrays.equals(a, e3));
k = 4;
int e4[] = {23, 5, 24, 15, 30};
move(a, k);
assertTrue(Arrays.equals(a, e4));
k = 5;
int e5[] = {23, 5, 24, 15, 30};
move(a, k);
assertTrue(Arrays.equals(a, e5));
k = 7;
int e6[] = {15, 30, 23, 5, 24};
move(a, k);
assertTrue(Arrays.equals(a, e6));
k = 29;
int e7[] = {30, 23, 5, 24, 15};
move(a, k);
assertTrue(Arrays.equals(a, e7));
}
}
|
| 返回顶楼 | |
