leetcode-384-打乱数组(shuffle an array)-java
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode-384-打乱数组(shuffle an array)-java,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3490字,纯文字阅读大概需要5分钟。
内容图文
题目及测试
package pid384;
/* Shuffle an Array
打乱一个没有重复元素的数组。
示例:
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();
*/
public class main {
public static void main(String[] args) {
int[][] testTable = {{1,2,3},{2,7,9,3,1},{7,10,4,3,1},{11,6,2,7}};
for (int[] ito : testTable) {
test(ito);
}
}
private static void test(int[] ito) {
Solution solution = new Solution(ito);
int[] rtn;
long begin = System.currentTimeMillis();
for (int i = 0; i < ito.length; i++) {
System.out.print(ito[i]+" ");
}
System.out.println();
//开始时打印数组
rtn = solution.shuffle();//执行程序
long end = System.currentTimeMillis();
System.out.println(ito + ": rtn=" );
System.out.println( " rtn=" );
for (int i = 0; i < rtn.length; i++) {
System.out.print(rtn[i]+" ");
}//打印结果几数组
rtn = solution.reset();//执行程序
System.out.println(ito + ": rtn=" );
System.out.println( " rtn=" );
for (int i = 0; i < rtn.length; i++) {
System.out.print(rtn[i]+" ");
}//打印结果几数组
System.out.println();
System.out.println("耗时:" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
解法1(成功,282ms,较慢)
在class中设置一个int数组作为源头
reset方法,返回一个copy的数组
shuffle方法,将源头数组一个个加入linkedlist
int index=(int)(Math.random()*i);
每次将list的这个index的数字取出加入结果数组
然后i–
package pid384;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class Solution {
int[] source;
public Solution(int[] nums) {
source=nums;
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
int[] result=Arrays.copyOf(source,source.length);
return result;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
List<Integer> list=new LinkedList<>();
int length=source.length;
if(length==0){
return null;
}
int[] result=new int[length];
for(int i=0;i<length;i++){
list.add(source[i]);
}
for(int i=length;i>0;i--){
int index=(int)(Math.random()*i);
result[length-i]=list.get(index);
list.remove(index);
}
return result;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
解法2(别人的)
这个题要用两个数组,一个存储原来的数据,一个存储工作的数据。
首次:不要用=(等号是把两个引用指向统一位置),要记得复制数组。
方法是:复制后,以i逆序遍历工作数组,可以在[0 - i]中随机选一个数,这个数是工作数组中被选中数的索引,然后将被选中的数与第i个数交换位置。
import java.util.Random;
class Solution {
private int[] originalNums;
private int[] currentNums;
public Solution(int[] nums) {
originalNums = nums;
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return originalNums;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
currentNums = Arrays.copyOf(originalNums, originalNums.length);
Random randNum = new Random();
for (int i = currentNums.length - 1; i >= 0; i--) {
int selectedElem = randNum.nextInt(i + 1);
int temp = currentNums[selectedElem];
currentNums[selectedElem] = currentNums[i];
currentNums[i] = temp;
}
return currentNums;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
内容总结
以上是互联网集市为您收集整理的leetcode-384-打乱数组(shuffle an array)-java全部内容,希望文章能够帮你解决leetcode-384-打乱数组(shuffle an array)-java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。