java - 如何在不使用 Collections.swap() 的情况下随机化 ArrayList?
问题描述
我被要求创建一个随机重新排列包含数组的列表的方法。该列表包含多个人员及其姓名和姓氏。我的问题是如何在不使用方法 swap() 的情况下将一个人(列表中包含两个元素 name 和 surname 的数组)移动到不同的索引?因为我们的列表不支持该方法。遗憾的是,我们不使用“官方”列表,而是将自己的列表编码如下:
public class List<ContentType> {
private class ListNode {
private ContentType contentObject;
private ListNode next;
private ListNode(ContentType pContent) {
contentObject = pContent;
next = null;
}
public ContentType getContentObject() {
return contentObject;
}
public void setContentObject(ContentType pContent) {
contentObject = pContent;
}
public ListNode getNextNode() {
return this.next;
}
public void setNextNode(ListNode pNext) {
this.next = pNext;
}
}
ListNode first;
ListNode last;
ListNode current;
public List() {
first = null;
last = null;
current = null;
}
public boolean isEmpty() {
return first == null;
}
public boolean hasAccess() {
return current != null;
}
public void next() {
if (this.hasAccess()) {
current = current.getNextNode();
}
}
public void toFirst() {
if (!isEmpty()) {
current = first;
}
}
public void toLast() {
if (!isEmpty()) {
current = last;
}
}
public ContentType getContent() {
if (this.hasAccess()) {
return current.getContentObject();
} else {
return null;
}
}
public void setContent(ContentType pContent) {
if (pContent != null && this.hasAccess()) {
current.setContentObject(pContent);
}
}
public void insert(ContentType pContent) {
if (pContent != null) {
if (this.hasAccess()) {
ListNode newNode = new ListNode(pContent);
if (current != first) {
ListNode previous = this.getPrevious(current);
newNode.setNextNode(previous.getNextNode());
previous.setNextNode(newNode);
} else {
newNode.setNextNode(first);
first = newNode;
}
} else {
if (this.isEmpty()) {
ListNode newNode = new ListNode(pContent);
first = newNode;
last = newNode;
}
}
}
}
public void append(ContentType pContent) {
if (pContent != null) {
if (this.isEmpty()) {
this.insert(pContent);
} else {
ListNode newNode = new ListNode(pContent);
last.setNextNode(newNode);
last = newNode;
}
}
}
public void concat(List<ContentType> pList) {
if (pList != this && pList != null && !pList.isEmpty()) {
if (this.isEmpty()) {
this.first = pList.first;
this.last = pList.last;
} else {
this.last.setNextNode(pList.first);
this.last = pList.last;
}
pList.first = null;
pList.last = null;
pList.current = null;
}
}
public void remove() {
if (this.hasAccess() && !this.isEmpty()) {
if (current == first) {
first = first.getNextNode();
} else {
ListNode previous = this.getPrevious(current);
if (current == last) {
last = previous;
}
previous.setNextNode(current.getNextNode());
}
ListNode temp = current.getNextNode();
current.setContentObject(null);
current.setNextNode(null);
current = temp;
if (this.isEmpty()) {
last = null;
}
}
}
private ListNode getPrevious(ListNode pNode) {
if (pNode != null && pNode != first && !this.isEmpty()) {
ListNode temp = first;
while (temp != null && temp.getNextNode() != pNode) {
temp = temp.getNextNode();
}
return temp;
} else {
return null;
}
}
public int length() {
int i = 0;
while(this.hasAccess()) {
i++;
next();
}
return i;
}
}
这是我想要的方法的版本,它应该通过多次交换对象来随机重新排列列表,但它显然不起作用。
public static void shuffleList(final List<String[]> list) {
int length = list.length();
Random random = new Random();
for (int i = 0; i < length; i++) {
// Swap index
int swap = i + random.nextInt(length - i);
// Store temporarily
String name1 = list.getContent()[0];
String surname1 = list.getContent()[1];
String[] temp1 = {mail1, pw1};
System.out.println(temp1);
for (int j = 0; j < swap; j++) {
list.next();
}
String name2 = list.getContent()[0];
String surname2 = list.getContent()[1];
String[] temp2 = {mail2, pw2};
// Set the values
list.setContent(temp1);
list.toFirst();
for (int k = 0; k < i; k++) {
list.next();
}
list.setContent(temp2);
}
}
如果有人可以帮助我找到一种方法来交换列表中的元素,我将非常高兴,这样我最终可以找到随机重新排列列表的方法。
谢谢你的每一个回答!:)
解决方案
I would suggest firstly converting your list to an array, so you have O(1)
random access, then shuffle this array and after that replace values in your list.
Here is a code
public class ListUtils {
/**
* Shuffles a list, leaving it's pointer on the first element.
*
* @param list list to shuffle
* @param rnd random number generator
*/
@SuppressWarnings({"unchecked"})
public static <T> void shuffleList(List<T> list, Random rnd) {
Object[] arr = toArray(list);
for (int i = arr.length; i > 1; --i) {
swap(arr, i - 1, rnd.nextInt(i));
}
list.toFirst();
for (Object o : arr) {
list.setContent((T) o);
list.next();
}
}
private static void swap(Object[] arr, int i, int j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static Object[] toArray(List<?> list) {
// length is O(n), makes sense to track size on every add, so it will be O(1)
list.toFirst();
int size = list.length();
Object[] result = new Object[size];
list.toFirst();
for (int i = 0; i < size; ++i) {
result[i] = list.getContent();
list.next();
}
return result;
}
public static void main(String[] args) {
List<String> l = new List<>();
l.append("a");
l.append("b");
l.append("c");
l.append("d");
shuffleList(l, new Random());
l.toFirst();
while (l.hasAccess()) {
System.out.println(l.getContent());
l.next();
}
}
}
推荐阅读
- swift - 在视图控制器中使用自定义 uiview
- android - # 在 https://developer.android.com/ 中是什么意思
- scala - 如何在火花数据帧中将其他情况转换为其他情况
- dependency-injection - 在没有依赖注入 (DI) 容器的情况下使用 ASP.NET 样板?
- laravel-controller - 更改控制器目录时未找到 Laravel 自定义控制器
- ios - 如何使用swift模仿与导航控制器的后退按钮相同的后退按钮动作?
- wordpress - 如何在另一个模板中加载 i 框架中的模板
- python - Python strptime missing some milliseconds when running script in different computer
- angular - 如何在不刷新数据的情况下将数据从一个组件传递到另一个组件(使用服务)
- javascript - 我在 reactjs 中有一个秒表,如何将每个数字添加到某种数组中以显示每个数字?