为了方便，我就以list为例：
算法思路
- 第一种方法的思路是：用set存储已经取过的下标，每次循环取的时候，判断是否已经取过
如果已经取过就跳过本次循环，一直到取num为止
这个方法不推荐使用，可能会发生死循环
如果每一次的数据值都是同一个，那么就是死循环了，虽然概论极其低，但是不代表没有
public static List getListUnique1(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 复制一份，以免对原数据造成影响
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Set<Integer> gotIndexs = new HashSet<>(num); // 以获取的下标
Random random = new Random();
while (gotIndexs.size() < num) {
int i = random.nextInt(_sources.size());
// 已经获取过了，跳过本次循环
if (gotIndexs.contains(i)) continue;
// 如果没有获取过，则放入数据
targetList.add(_sources.get(i));
gotIndexs.add(i);
}
return targetList;
}
- 第二种方法思路是：每一次循环取完数据后，从目标list中移除本次取的数据，list的大小也变小了，下一次循环产生的随机数最大值也是list的size，所以不会发生越界问题。
public static List getListUnique2(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 复制一份，以免对原数据造成影响
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Random random = new Random();
for (int k = 0; k < num; k++) {
int i = random.nextInt(_sources.size());
targetList.add(_sources.get(i));
// 取完后，从目标list内移除该数据
_sources.remove(i);
}
return targetList;
}
- 第三中方法思路：每一次循环取完数据后，把list size - k -1 的元素 放到本次取到的index位置，下次循环的随机数最大值为list size - k
public static List getListUnique3(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 复制一份，以免对原数据造成影响
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Random random = new Random();
for (int k = 0; k < num; k++) {
int i = random.nextInt(_sources.size() - k);
Object tmp = _sources.get(i);
targetList.add(tmp);
// 取完后，把list size - k 的元素 放到本次取到的index位置
_sources.set(i, _sources.get(_sources.size() - k - 1));
}
return targetList;
}
分析
- 第一种方法，不推荐使用，这里就不说了
- 如果list的实现为ArrayList，那么第三种方法会比第二种好，因为在list移除的时候，实际上发生的数组的复制，有兴趣的可以了解ArrayList的实现。
- 如果list的实现为LinkedList，那么第三种方法和第二种方法没有太多的差别
- 上面的算法实现还可以优化，例如，不用复制一份原数据，直接使用原数据的下标形成新的List，然后对下标进行随机取，取完后在根据下标去原list中取对应的数据。
- 上面只给了List的实现，那数组的实现呢？方法有两种：
- 最简单的是把数组转换为ArrayList，然后就一样了
- 根据上面的思路，用数组实现。
各位，如果你有什么更好的想法，也欢迎评论
附源码
/**
* 获取不重复下标的元素
*/
public class UniqueCollectionIndex {
public static void main(String[] args) {
int num = 6;
List list1 = new ArrayList();
// 放入A-Z做测试
for (int i = 65; i < 91; i++) {
list1.add((char) i);
}
System.out.println(getListUnique1(list1, num));
System.out.println(getListUnique2(list1, num));
System.out.println(getListUnique3(list1, num));
}
//***** list *******
/**
* <p style="color:red">不推荐使用，可能会发生死循环</p>
* 用set存储已经取过的下标，每次循环取的时候，判断是否已经取过
* 如果已经取过就跳过本次循环，一直到取num为止
*
* @param sources 目标list
* @param num 获取元素的数量
* @return 获取的list
*/
public static List getListUnique1(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 复制一份，以免对原数据造成影响
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Set<Integer> gotIndexs = new HashSet<>(num); // 以获取的下标
Random random = new Random();
while (gotIndexs.size() < num) {
int i = random.nextInt(_sources.size());
// 已经获取过了，跳过本次循环
if (gotIndexs.contains(i)) continue;
// 如果没有获取过，则放入数据
targetList.add(_sources.get(i));
gotIndexs.add(i);
}
return targetList;
}
/**
* 每一次循环取完数据后，从目标list中移除本次取的数据
*
* @param sources 目标list
* @param num 获取元素的数量
* @return 获取的list
*/
public static List getListUnique2(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 复制一份，以免对原数据造成影响
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Random random = new Random();
for (int k = 0; k < num; k++) {
int i = random.nextInt(_sources.size());
targetList.add(_sources.get(i));
// 取完后，从目标list内移除该数据
_sources.remove(i);
}
return targetList;
}
/**
* 每一次循环取完数据后，把list size - k -1 的元素 放到本次取到的index位置，
* 下次循环的随机数最大值为list size - k
*
* @param sources 目标list
* @param num 获取元素的数量
* @return 获取的list
*/
public static List getListUnique3(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 复制一份，以免对原数据造成影响
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Random random = new Random();
for (int k = 0; k < num; k++) {
int i = random.nextInt(_sources.size() - k);
Object tmp = _sources.get(i);
targetList.add(tmp);
// 取完后，把list size - k 的元素 放到本次取到的index位置
_sources.set(i, _sources.get(_sources.size() - k - 1));
}
return targetList;
}
}
网友评论