算法热题:打乱数组
每日简短一刷,保持手感系列
题目:
给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象 int[] reset() 重设数组到它的初始状态并返回 int[] shuffle() 返回数组随机打乱后的结果
示例:
输入 ["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
例子:
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如,返回 [3, 1, 2]
solution.reset();// 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如,返回 [1, 3, 2]
提示:
1 <= nums.length <= 200 -106 <= nums[i] <= 106 nums 中的所有元素都是 唯一的 最多可以调用 5 * 104 次 reset 和 shuffle
今天这题目比较简单和直白。
随机就想到Random这个伪随机类来实现就行了。
然后需要定义两个数组,一个来保存初始顺序的数组,它是不变的。
另一个数组则存储每次打乱顺序的值。
答案:
解法一
classSolution{
privateint[] oriNums;
privateint[] shuffles;
private Random rand;
publicSolution(int[] nums){
oriNums = nums.clone();
shuffles = nums;
rand = new Random();
}
/** Resets the array to its original configuration and return it. */
publicint[] reset() {
return oriNums;
}
/** Returns a random shuffling of the array. */
publicint[] shuffle() {
List<Integer> list = copyArrayAsList();
for (int i = 0 ; i < shuffles.length; i++) {
int index = rand.nextInt(list.size());
shuffles[i] = list.get(index);
list.remove(index);
}
return shuffles;
}
private List<Integer> copyArrayAsList(){
List<Integer> list = new ArrayList();
for (int i = 0; i < oriNums.length; i++) {
list.add(oriNums[i]);
}
return list;
}
}
注意点:
shuffle时间复杂度是n平方,因为 remove 需要遍历 list 列表的。
解法二
那就优化 remove 地方,解法一是利用一个list来移除已经被挑选的值,防止重复选择,这里可以做一波优化。
将它变成数组元素的交换,利用下标的递进来防止重复选择。
classSolution{
privateint[] oriNums;
privateint[] shuffles;
private Random rand;
publicSolution(int[] nums){
oriNums = nums.clone();
shuffles = nums;
rand = new Random();
}
/** Resets the array to its original configuration and return it. */
publicint[] reset() {
return oriNums;
}
/** Returns a random shuffling of the array. */
publicint[] shuffle() {
shuffles = oriNums.clone(); // 保证起始数据都是原有的顺序
for (int i = 0 ; i < shuffles.length; i++) {
int index = rand.nextInt(shuffles.length - i) + i;
swap(i, index);
}
return shuffles;
}
privatevoidswap(int a, int b){
int temp = shuffles[index];
shuffles[index] = shuffles[i];
shuffles[i] = temp;
}
}
这样时间复杂度就变成 O(n)了。
关键词
元素
数组
算法
List
解法
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。