2021-11-11:打乱数组。给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。实现 Solution cl
2023-03-14 22:57:18 时间
2021-11-11:打乱数组。给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。实现 Solution class:Solutio(int[] nums) 使用整数数组 nums 初始化对象;int[] reset() 重设数组到它的初始状态并返回;int[] shuffle() 返回数组随机打乱后的结果 。力扣384。
答案2021-11-11:
第1次,1到N-1取随机数i1,[i1]与[N-1]交换。
第2次,1到N-2取随机数i2,[i2]与[N-2]交换。
遍历下去,就是打乱的数组了。
时间复杂度:O(N)。
额外空间复杂度:O(N)。因为有重置功能。
代码用golang编写。代码如下:
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().UnixNano())
arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
c := Constructor(arr)
fmt.Println(c.Shuffle())
}
type Solution struct {
origin []int
shuffle []int
N int
}
func Constructor(nums []int) Solution {
res := Solution{}
res.origin = nums
res.N = len(nums)
res.shuffle = make([]int, res.N)
for i := 0; i < res.N; i++ {
res.shuffle[i] = res.origin[i]
}
return res
}
func (this *Solution) Reset() []int {
return this.origin
}
func (this *Solution) Shuffle() []int {
for i := this.N - 1; i >= 0; i-- {
//int r = (int) (Math.random() * (i + 1));
r := rand.Intn(i + 1)
tmp := this.shuffle[r]
this.shuffle[r] = this.shuffle[i]
this.shuffle[i] = tmp
}
return this.shuffle
}
执行结果如下:
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class34/Problem_0384_ShuffleAnArray.java)
相关文章
- 框架解读:中国互联网年度趋势报告(附128PPT下载)
- 开源科学计算包NumPy 宣布将停止支持 Python 2
- TIOBE 11 月编程语言排行榜:iOS开发真没人要了?OC、Swift接连下滑
- Cors跨域(二):实现跨域Cookie共享的三要素
- 从java1到java9每个版本都有什么新特性?花费五分钟全面了解
- 如何分析博客中最流行的编程语言
- 为什么需要Go这样一个新编程语言?
- 120 行代码帮你了解 Webpack 下的 HMR 机制
- R: 学习Gradient Boosting算法,提高预测模型准确率
- 干货 -Gulp打包支持await/async语法
- 可视化学习 Go并发编程
- 盘点| NIPS(神经信息处理系统进展大会)机器学习相关内容
- 5个最重要的分布式系统设计模式
- nuclio:新的无服务器化超级英雄
- 一行可以让项目启动快 70% 以上的代码
- 多线程进程fork出来的进程是单线程还是多线程?
- 核心算法|谷歌如何从网络的大海里捞到针
- 实时股票预测的开源参考结构
- Docker系列—简介概述
- 简单的方式发送邮件,让程序出错自动发邮件