问题：将一个n元一维向量向左旋转i个位置。如，当n=8且i=3时，向量abcdefgh旋转为defghabc.求解决方案。
1. 首先将x的前i个元素复制到一个临时数组中，然后将余下的n-i个元素向左移动i个位置，最后将最初的i个元素从临时数组中复制到x中余下的位置。但是，这种办法使用的i个额外位置产生了过大的存储空间消耗。
2. 定义一个函数将x向左旋转一个位置然后调用该函数i次。但该方法又产生了过多的运行时间消耗。
3. 要在有限的资源内解决该问题，显然需要更复杂的程序。有一个成功的方法有点像精巧的杂技动作：移动x[0]到临时变量t,然后移动x[i]至x[0],x[2i]至x[i],依次类推（将x中的所有下标对n取模），直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。
4. 我们将问题看成把数组ab转换成ba，同时假定我们拥有一个函数可以将数组中的特定部分元素求逆。从ab开始，先对a求逆，得到ar b,然后对b求逆，得到ar br ，然后整体求逆，得到（ar b r）r 。此时就是ba。
杂技算法的代码：
|
package bczj.chapter2;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import com.util.MyList;
/**
*
*
* Title:杂技算法 <br>
* Description: <br>
* Copyright: Copyright (c) 2007<br>
* Company:xx有限公司<br>*
* @author yingkh
* @version 1.0
* @date 2010-8-3
*/
public class Acrobatics {
public Acrobatics(){
}
public List<String> rotation(List<String> list, int rotdist) {
//最大公约数(Greatest common divisor)
int m = gcd (rotdist,list.size());
int j = 0;
for(int i=0; i<m; i++) {
String temp = list.get(i);
j = i;
while(true) {
int k = j + rotdist;
if(k >= list.size()) {
k -= list.size();
}
if( k== i) {
break;
}
list.set(j, list.get(k));
j = k;
}
list.set(j, temp);
}
return list;
}
//求最大公约数
private int gcd(int i, int j) {
while(i != j) {
if(i > j){
i -= j;
}else {
j -= i;
}
}
return i;
}
/**
* @param args
*/
public static void main(String[] args) {
Acrobatics ac = new Acrobatics();
MyList myList = new MyList();
List list = myList.createStringList(6);
List result = ac.rotation(list, 3);
myList.print(result);
}
}
/*
* 编程珠玑：将一个n元一维向量向左旋转i个位置。如当n=8,i=3时，向量abcdefgh旋转为
* defghabc.
*
* */
|
旋转算法：
|
package bczj.chapter2;
import java.util.Collections;
import java.util.List;
import com.util.MyList;
/**
*
*
* Title:翻转数组 <br>
* Description: <br>
* Copyright: Copyright (c) 2007<br>
* Company:XX限公司<br> *
* @author yingkh
* @version 1.0
* @date 2010-8-3
*/
public class InverseArray {
public InverseArray() {
}
//翻转元素
private List<String> reverseList(List<String> list, int begin, int end) {
if(begin <= end) {
for(int i = begin; i < end; i++,end--) {
if(i<end-1) {
String temp = list.get(i);
list.set(i, list.get(end-1));
list.set(end-1, temp);
}
}
}
return list;
}
/**
* @param args
*/
public static void main(String[] args) {
Acrobatics ac = new Acrobatics();
MyList myList = new MyList();
List list = myList.createStringList(10);
InverseArray inverseArray = new InverseArray();
inverseArray.reverseList(list, 0, 5);
inverseArray.reverseList(list, 5, 10);
inverseArray.reverseList(list, 0, 10);
myList.print(list);*/
}
}
|
公用的myList类：
|
package com.util;
import java.util.ArrayList;
import java.util.List;
public class MyList {
public MyList() {
}
//产生String类型的list
public List<String> createStringList(int length) {
List<String> list = new ArrayList<String>();
for(int i=0; i<length ;i++){
list.add(String.valueOf(i));
}
return list;
}
//打印list
public void print(List<String> list) {
for(int i=0; i<list.size() ;i++) {
System.out.println("第"+i+"个元素为： "+list.get(i));
}
}
}
|
其实Collection中已经有这个算法了，Collections.rotate()方法。
rotate
public static void rotate(List<?> list,int distance)根据指定的距离轮换指定列表中的元素。调用此方法后，对于 0 和 list.size()-1（包括）之间的所有 i 值，索引 i 处的元素将是以前位于索引 (i - distance) mod list.size() 处的元素。（此方法对列表的大小没有任何影响。） 例如，假设 list 包含 [t, a, n, k, s]。在调用 Collections.rotate(list, 1)（或 llections.rotate(list, -4)）之后，list 将包含 [s, t, a, n, k]。 注意，此方法用于子列表时非常有用，可以在保留其余元素顺序的同时，在列表中移动一个或多个元素。例如，以下语句可以将索引 j 处的元素向前移动到位置 k 上（k 必须大于等于 j）： Collections.rotate(list.subList(j, k+1), -1);为了具体说明这一点，假设 list 包含 [a, b, c, d, e]。要将索引 1 处的元素（b）向前移动两个位置，请执行以下调用： Collections.rotate(l.subList(1, 4), -1); 得到的列表是 [a, c, d, b, e]。
我们来看一下它的源码吧：
|
private static final int ROTATE_THRESHOLD = 100;
public static void rotate(List<?> list, int distance) {
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1((List)list, distance);
else
rotate2((List)list, distance);
}
private static <T> void rotate1(List<T> list, int distance) {
int size = list.size();
if (size == 0)
return;
distance = distance % size;
if (distance < 0)
distance += size;
if (distance == 0)
return;
for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
T displaced = list.get(cycleStart);
int i = cycleStart;
do {
i += distance;
if (i >= size)
i -= size;
displaced = list.set(i, displaced);
nMoved ++;
} while(i != cycleStart);
}
}
private static void rotate2(List<?> list, int distance) {
int size = list.size();
if (size == 0)
return;
int mid = -distance % size;
if (mid < 0)
mid += size;
if (mid == 0)
return;
reverse(list.subList(0, mid));
reverse(list.subList(mid, size));
reverse(list);
}
|
很有趣，当list的长度小于100时，list默认用的是杂技算法，否则用的是翻转算法。
另外我们看一下list的reverse方法，写的很精妙：
|
public static void reverse(List<?> list) {
int size = list.size();
if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
swap(list, i, j);
} else {
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}
|
同样，swap方法：
|
public static void swap(List<?> list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
}
|
ArrayList的set方法：
|
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
|
不得不感叹java的源码，确实精妙。
分享到：
相关推荐
编程中的一本关于算法的好书。
《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》一书深入探讨了ASP.NET 2.0的核心概念和技术，旨在帮助开发者熟练掌握这一平台。 在ASP.NET 2.0中，控件是构建用户界面的关键组件。它们包括服务器控件和HTML控件，...
编程珠玑-[美]乔恩美特利.mobi、kindle文档、第二版修订版
### 编程珠玑-中文第二版 #### 知识点概述 《编程珠玑-中文第二版》是一本在计算机科学领域内享有极高声誉的经典著作。本书虽然篇幅不长，但却以其深刻的见解和丰富的内涵深受广大程序员和技术爱好者的推崇。通过...
《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》是一本深入探讨ASP.NET 2.0技术的专业书籍，由该领域的专家，即微软最有价值专家（MVP）撰写。这本书旨在帮助开发者充分理解和掌握ASP.NET 2.0的核心概念，提升其在...
这本书“ASP.NET 2.0编程珠玑--来自MVP的权威开发指南”深入讲解了这个框架的关键特性和最佳实践，旨在帮助开发者充分利用其功能。 在ASP.NET 2.0中，最重要的改进之一是页面生命周期管理。与前一版本相比，2.0版...
《编程珠玑（第 2版·修订版）》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者JonBentley以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法，而这些正是程序员...
《编程珠玑》之所以成为许多程序员的案头书，不仅因为它涵盖了编程中的许多重要主题，如算法设计、数据结构、性能优化以及编程实践，更重要的是，它教会我们一种解决问题的思维。Jon Bentley的每一篇“珍珠”，都像...
无书签,
本书“ASP.NET+2.0编程珠玑--开发指南”是针对这个版本的专业指南，由MVP（Microsoft最有价值专家）撰写，旨在帮助开发者深入理解和掌握ASP.NET 2.0的核心概念和技术。 书中可能涵盖了以下关键知识点： 1. **ASP...
### 编程珠玑：算法与数据结构精要 #### 核心概念解析 在《编程珠玑》这本书中，作者深入浅出地探讨了算法和数据结构的重要性及其实际应用。该书被认为是学习计算机科学基础知识不可或缺的经典之作。下面将根据...
编程珠玑，第二版，高清版，带目录,对学习编程有一些帮助
此压缩包文件提供的"ASP.NET+2.0编程珠玑--来自MVP的权威开发指南"是一本深入探讨ASP.NET 2.0技术的书籍，可能包含了以下关键知识点： 1. **ASP.NET 2.0概述**：ASP.NET 2.0在ASP.NET 1.x的基础上进行了许多改进，...
NULL 博文链接：https://philoscience.iteye.com/blog/1010964