為了方便仑荐,我就以list為例:
算法思路
- 第一種方法的思路是:用set存儲已經(jīng)取過的下標(biāo)荚坞,每次循環(huán)取的時候虎谢,判斷是否已經(jīng)取過
如果已經(jīng)取過就跳過本次循環(huán)科展,一直到取num為止
這個方法不推薦使用,可能會發(fā)生死循環(huán)
如果每一次的數(shù)據(jù)值都是同一個堪旧,那么就是死循環(huán)了削葱,雖然概論極其低,但是不代表沒有
public static List getListUnique1(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份淳梦,以免對原數(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)獲取過了析砸,跳過本次循環(huán)
if (gotIndexs.contains(i)) continue;
// 如果沒有獲取過,則放入數(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)生的隨機數(shù)最大值也是list的size陨囊,所以不會發(fā)生越界問題弦疮。
public static List getListUnique2(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份,以免對原數(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)的隨機數(shù)最大值為list size - k
public static List getListUnique3(List sources, int num) {
if (sources.size() <= num) {
return sources;
}
// 復(fù)制一份压语,以免對原數(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;
}
分析
- 第一種方法,不推薦使用胎食,這里就不說了
- 如果list的實現(xiàn)為ArrayList扰才,那么第三種方法會比第二種好,因為在list移除的時候厕怜,實際上發(fā)生的數(shù)組的復(fù)制衩匣,有興趣的可以了解ArrayList的實現(xiàn)蕾总。
- 如果list的實現(xiàn)為LinkedList,那么第三種方法和第二種方法沒有太多的差別
- 上面的算法實現(xiàn)還可以優(yōu)化琅捏,例如生百,不用復(fù)制一份原數(shù)據(jù),直接使用原數(shù)據(jù)的下標(biāo)形成新的List午绳,然后對下標(biāo)進行隨機取置侍,取完后在根據(jù)下標(biāo)去原list中取對應(yīng)的數(shù)據(jù)。
- 上面只給了List的實現(xiàn)拦焚,那數(shù)組的實現(xiàn)呢蜡坊?方法有兩種:
- 最簡單的是把數(shù)組轉(zhuǎn)換為ArrayList,然后就一樣了
- 根據(jù)上面的思路赎败,用數(shù)組實現(xiàn)秕衙。
各位,如果你有什么更好的想法僵刮,也歡迎評論
附源碼
/**
* 獲取不重復(fù)下標(biāo)的元素
*/
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">不推薦使用据忘,可能會發(fā)生死循環(huán)</p>
* 用set存儲已經(jīng)取過的下標(biāo),每次循環(huán)取的時候搞糕,判斷是否已經(jīng)取過
* 如果已經(jīng)取過就跳過本次循環(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ù)制一份,以免對原數(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)獲取過了窍仰,跳過本次循環(huán)
if (gotIndexs.contains(i)) continue;
// 如果沒有獲取過汉规,則放入數(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ù)制一份驹吮,以免對原數(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)的隨機數(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ù)制一份啄枕,以免對原數(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;
}
}