為了方便，我就以list為例：
算法思路
- 第一種方法的思路是：用set存儲(chǔ)已經(jīng)取過(guò)的下標(biāo)，每次循環(huán)取的時(shí)候，判斷是否已經(jīng)取過(guò)
如果已經(jīng)取過(guò)就跳過(guò)本次循環(huán)，一直到取num為止
這個(gè)方法不推薦使用，可能會(huì)發(fā)生死循環(huán)
如果每一次的數(shù)據(jù)值都是同一個(gè)，那么就是死循環(huán)了，雖然概論極其低，但是不代表沒(méi)有
public static List getListUnique1(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份，以免對(duì)原數(shù)據(jù)造成影響
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Set<Integer> gotIndexs = new HashSet<>(num); // 以獲取的下標(biāo)
Random random = new Random();
while (gotIndexs.size() < num) {
int i = random.nextInt(_sources.size());
// 已經(jīng)獲取過(guò)了，跳過(guò)本次循環(huán)
if (gotIndexs.contains(i)) continue;
// 如果沒(méi)有獲取過(guò)，則放入數(shù)據(jù)
targetList.add(_sources.get(i));
gotIndexs.add(i);
}
return targetList;
}
- 第二種方法思路是：每一次循環(huán)取完數(shù)據(jù)后，從目標(biāo)list中移除本次取的數(shù)據(jù)，list的大小也變小了，下一次循環(huán)產(chǎn)生的隨機(jī)數(shù)最大值也是list的size，所以不會(huì)發(fā)生越界問(wèn)題。
public static List getListUnique2(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份，以免對(duì)原數(shù)據(jù)造成影響
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));
// 取完后，從目標(biāo)list內(nèi)移除該數(shù)據(jù)
_sources.remove(i);
}
return targetList;
}
- 第三中方法思路：每一次循環(huán)取完數(shù)據(jù)后，把list size - k -1 的元素 放到本次取到的index位置，下次循環(huán)的隨機(jī)數(shù)最大值為list size - k
public static List getListUnique3(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份，以免對(duì)原數(shù)據(jù)造成影響
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;
}
分析
- 第一種方法，不推薦使用，這里就不說(shuō)了
- 如果list的實(shí)現(xiàn)為ArrayList，那么第三種方法會(huì)比第二種好，因?yàn)樵趌ist移除的時(shí)候，實(shí)際上發(fā)生的數(shù)組的復(fù)制，有興趣的可以了解ArrayList的實(shí)現(xiàn)。
- 如果list的實(shí)現(xiàn)為L(zhǎng)inkedList，那么第三種方法和第二種方法沒(méi)有太多的差別
- 上面的算法實(shí)現(xiàn)還可以?xún)?yōu)化，例如，不用復(fù)制一份原數(shù)據(jù)，直接使用原數(shù)據(jù)的下標(biāo)形成新的List，然后對(duì)下標(biāo)進(jìn)行隨機(jī)取，取完后在根據(jù)下標(biāo)去原list中取對(duì)應(yīng)的數(shù)據(jù)。
- 上面只給了List的實(shí)現(xiàn)，那數(shù)組的實(shí)現(xiàn)呢？方法有兩種：
- 最簡(jiǎn)單的是把數(shù)組轉(zhuǎn)換為ArrayList，然后就一樣了
- 根據(jù)上面的思路，用數(shù)組實(shí)現(xiàn)。
各位，如果你有什么更好的想法，也歡迎評(píng)論
附源碼
/**
* 獲取不重復(fù)下標(biāo)的元素
*/
public class UniqueCollectionIndex {
public static void main(String[] args) {
int num = 6;
List list1 = new ArrayList();
// 放入A-Z做測(cè)試
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">不推薦使用，可能會(huì)發(fā)生死循環(huán)</p>
* 用set存儲(chǔ)已經(jīng)取過(guò)的下標(biāo)，每次循環(huán)取的時(shí)候，判斷是否已經(jīng)取過(guò)
* 如果已經(jīng)取過(guò)就跳過(guò)本次循環(huán)，一直到取num為止
*
* @param sources 目標(biāo)list
* @param num 獲取元素的數(shù)量
* @return 獲取的list
*/
public static List getListUnique1(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份，以免對(duì)原數(shù)據(jù)造成影響
List _sources = new ArrayList(sources);
List targetList = new ArrayList(num);
Set<Integer> gotIndexs = new HashSet<>(num); // 以獲取的下標(biāo)
Random random = new Random();
while (gotIndexs.size() < num) {
int i = random.nextInt(_sources.size());
// 已經(jīng)獲取過(guò)了，跳過(guò)本次循環(huán)
if (gotIndexs.contains(i)) continue;
// 如果沒(méi)有獲取過(guò)，則放入數(shù)據(jù)
targetList.add(_sources.get(i));
gotIndexs.add(i);
}
return targetList;
}
/**
* 每一次循環(huán)取完數(shù)據(jù)后，從目標(biāo)list中移除本次取的數(shù)據(jù)
*
* @param sources 目標(biāo)list
* @param num 獲取元素的數(shù)量
* @return 獲取的list
*/
public static List getListUnique2(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份，以免對(duì)原數(shù)據(jù)造成影響
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));
// 取完后，從目標(biāo)list內(nèi)移除該數(shù)據(jù)
_sources.remove(i);
}
return targetList;
}
/**
* 每一次循環(huán)取完數(shù)據(jù)后，把list size - k -1 的元素 放到本次取到的index位置，
* 下次循環(huán)的隨機(jī)數(shù)最大值為list size - k
*
* @param sources 目標(biāo)list
* @param num 獲取元素的數(shù)量
* @return 獲取的list
*/
public static List getListUnique3(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份，以免對(duì)原數(shù)據(jù)造成影響
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;
}
}
