首页
学习
活动
专区
圈层
工具
发布

- 从长度为m的int数组中随机取出n个元素,每次取的元素都是之前未取过的

题目:从长度为m的int数组中随机取出n个元素,每次取的元素都是之前未取过的 Fisher-Yates洗牌算法是由 Ronald A.Fisher和Frank Yates于1938年发明的,后来被Knuth...用洗牌算法思路从1、2、3、4、5这5个数中,随机取一个数 4被抽中的概率是1/5 5被抽中的概率是1/4 * 4/5 = 1/5 2被抽中的概率是1/3 * 3/4 *...= new ArrayList(); for (int i = 1; i n; i++) { list.add(i); } for (int i = 0...该算法的基本思想和 Fisher 类似,每次从未处理的数据中随机取出一个数字,然后把该数字放在数组的尾部,即数组尾部存放的是已经处理过的数字。...时间复杂度为O(n), 空间复杂度为O(n) //O(N)time //O(N)space void knuth(int n, int m) { int[] arr = new int[n];

3.5K10

2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复比如,arr =

2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复比如,arr = 4, 2, 0, 3, 10 1 2 3 4把0想象成洞,任何非0数字都可以来到这个洞里,然后在原本的位置留下洞比如...4这个数字,来到0所代表的洞里,那么数组变成 : arr = 0, 2, 4, 3, 1也就是原来的洞被4填满,4走后留下了洞任何数字只能搬家到洞里,并且走后留下洞通过搬家的方式,想变成有序的,有序有两种形式比如...对于第二种有序情况,我们可以先倒序遍历数组,找出每个数需要移动的最小距离,从而计算出需要移动的次数。最后比较这两种情况下的最小搬动次数,返回较小值即可。...golang代码如下:package mainimport "fmt"func sortArray(nums []int) int {// 长度n// ans1 : 0 1 2 3 4 .......ans2}func main() {nums := []int{4, 2, 0, 3, 1}ans := sortArray(nums)fmt.Println(ans) // 输出 3}图片rust代码如下

1.8K00
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    Python-求1到n的一个乱序数组里面缺失的一个值

    当时看到这题的时候卡了一下想着排序,想了想用数学的思想去解决它是个更明智的方法 按照题目意思,我可以通过等差数列的计算公式计算出1到n的和,然后通过一个O(n)的sum过程,计算当前序列的总和,然后将等差数列的和减去当前序列的和...,就是当前序列所缺失了的值 #-*-coding:utf8;-*- import random print("This is console module") def generate_numarray...(n): array=[x for x in range(1,n+1)] array.remove(random.randint(1,len(array)-1)) return array...n=5 #生成目标数组 arr= generate_numarray(n) p=(n*(n+1))/2-sum(arr) print(arr) print('求和:',sum(arr)) print('...缺失值:',int(p)) (adsbygoogle = window.adsbygoogle || []).push({});

    1.3K20

    2021-07-27:给定一个数组arr,长度为N,arr中的值只有1

    2021-07-27:给定一个数组arr,长度为N,arr中的值只有1,2,3三种。...那么arr整体就代表汉诺塔游戏过程中的一个状况。如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1。如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况。...福大大 答案2021-07-27: 1-7的汉诺塔问题。 1-6左→中。 7左→右。 1-6中→右。 单决策递归。 k层汉诺塔问题,是2的k次方-1步。 时间复杂度:O(N)。...) int { N := len(arr) return step(arr, N-1, 1, 3, 2) } // 0...index这些圆盘,arr[0..index] index+...other // arr[0..index]这些状态,是index+1层汉诺塔问题的,最优解第几步 func step(arr []int, index int, from int, to int, other

    2K10

    2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m , 数组下标 从 1 开始 计数。

    2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m , 数组下标 从 1 开始 计数。 初始时,你的分数为 0 。...在第 i 步操作(从 1 开始 计数)中,需要: 选择数组 nums 开头处或者末尾处 的整数 x 。 你获得 multipliers[i] * x 分,并累加到你的分数中。...将 x 从数组 nums 中移除。 在执行 m 步操作后,返回 最大 分数。 力扣1770。 答案2022-04-09: 样本对应模型。 代码用golang编写。...(A, B []int) int { if len(A) == 0 || len(B) == 0 || len(A) < len(B) { return 0 } N := len(A...) M := len(B) dp := make([][]int, M+1) for i := 0; i 1; i++ { dp[i] = make([]int, M+1)

    95440

    2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m , 数组下标 从 1 开始 计数。

    2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m , 数组下标 从 1 开始 计数。 初始时,你的分数为 0 。...在第 i 步操作(从 1 开始 计数)中,需要: 选择数组 nums 开头处或者末尾处 的整数 x 。 你获得 multipliersi * x 分,并累加到你的分数中。...将 x 从数组 nums 中移除。 在执行 m 步操作后,返回 最大 分数。 力扣1770。 答案2022-04-09: 样本对应模型。 代码用golang编写。...(A, B []int) int { if len(A) == 0 || len(B) == 0 || len(A) < len(B) { return 0 } N := len(A) M...:= M - 1; L >= 0; L-- { for j := L + 1; j <= M; j++ { R := N - M + j - 1 indexB := L + N - R

    90110

    2022-04-18:things是一个N*3的二维数组,商品有N件,商品编号从1~N, 比如things =

    2022-04-18:things是一个N*3的二维数组,商品有N件,商品编号从1~N, 比如things[3] = [300, 2, 6], 代表第3号商品:价格300,重要度2,它是6号商品的附属商品...,它才能被购买, 任何一个附属商品,只会有1个主商品, 任何一个主商品的附属商品数量,不会超过2件, 主商品和附属商品的层级最多有2层。...给定二维数组things、钱数money,返回整体花费不超过money的情况下,最大的收益总和。 答案2022-04-18: 本来想用rust写的,但老是编译不通过,实在没辙。...n++ } } return n } func maxScore(things [][][]int, n, money int) int { dp := make([][]int,...func process(things [][][]int, n, index, rest int, dp [][]int) int { if rest < 0 { return -1

    67530

    2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复比如,arr = [4, 2, 0, 3,

    2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复 比如,arr = [4, 2, 0, 3, 1] 0 1 2 3 4 把0想象成洞...,任何非0数字都可以来到这个洞里,然后在原本的位置留下洞 比如4这个数字,来到0所代表的洞里,那么数组变成 : arr = [0, 2, 4, 3, 1] 也就是原来的洞被4填满,4走后留下了洞 任何数字只能搬家到洞里...对于第二种有序情况,我们可以先倒序遍历数组,找出每个数需要移动的最小距离,从而计算出需要移动的次数。 3. 最后比较这两种情况下的最小搬动次数,返回较小值即可。 注意事项: 1....# golang代码如下: package main import "fmt" func sortArray(nums []int) int { // 长度n // ans1 : 0 1 2...]int{4, 2, 0, 3, 1} ans := sortArray(nums) fmt.Println(ans) // 输出 3 } # rust代码如下: fn sort_array(

    1.1K30

    将判断 NSArray 数组是否包含指定元素的时间复杂度从 O(n) 降为 O(1)

    前言 NSArray 获取指定 元素 的位置 或者 判断是否存在指定的 元素 的时间复杂度是 O(n)(包含特定元素时,平均耗时是 O(n/2),如果不包含特定元素,耗时是 O(n))。...当我们需要频繁进行该操作时,可能会存在较大的性能问题。 该问题背后的原因很简单。官方文档明确指出 NSArray 从第 0 位开始依次判断是否相等,所以判断次数是 n (n 等于数组长度) ?...image 本文会介绍一个特别的方案,通过将数组转为字典,我们可以将时间复杂度降低到 O(1) 级别。...ID 键(ID 键总是从 0 开始)。...: 字典的 键 是数组存储的 元素 该设计方式可以保证后续通过 objectForKey: 判断是否存在指定的 元素 字典的 值 是 数组的 索引值 该规则保证字典可以恢复为数组 // 将数组转为字典

    2.8K20

    2023-02-12:给定正数N,表示用户数量,用户编号从0~N-1, 给定正数M,表示实验数量,实验编号从0~M-1, 给定长度为N的二维数组A, A

    2023-02-12:给定正数N,表示用户数量,用户编号从0~N-1,给定正数M,表示实验数量,实验编号从0~M-1,给定长度为N的二维数组A,Ai = { a, b, c }表示,用户i报名参加了a号...、b号、c号实验,给定正数Q,表示查询的条数给定长度为Q的二维数组B,Bi = { e, f }表示,第i条查询想知道e号、f号实验,一共有多少人(去重统计)。...返回每一条查询的结果数组。数据描述 : 1 N 1 1 的所有实验编号数量(也就是二维数组B,行*列的规模) n as i64 + 1) as u32; } else { n2 = n as u32; } let mut n = n2; n = (n & 0x55555555

    1.1K00

    2021-07-27:给定一个数组arr,长度为N,arr中的值只有1,2,3三种。arr == 1,代表汉诺塔问题中,从

    2021-07-27:给定一个数组arr,长度为N,arr中的值只有1,2,3三种。...那么arr整体就代表汉诺塔游戏过程中的一个状况。如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1。如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况。...福大大 答案2021-07-27: 1-7的汉诺塔问题。 1. 1-6左→中。 2. 7左→右。 3. 1-6中→右。 单决策递归。 k层汉诺塔问题,是[2的k次方-1]步。 时间复杂度:O(N)。...) int { N := len(arr) return step(arr, N-1, 1, 3, 2) } // 0...index这些圆盘,arr[0..index] index+...other // arr[0..index]这些状态,是index+1层汉诺塔问题的,最优解第几步 func step(arr []int, index int, from int, to int, other

    1.5K30

    用go语言,你要爬一段共有 n+1 级的台阶,编号从 0 到 n。给定一个长度为 n、下标从 1 开始的数组 costs,其中 co

    用go语言,你要爬一段共有 n+1 级的台阶,编号从 0 到 n。...给定一个长度为 n、下标从 1 开始的数组 costs,其中 costs[i] 表示第 i 级台阶自身的费用(第 0 级没有对应的 costs 项)。...初始位于台阶 0,累计费用从 0 开始。 返回到达台阶 n 时可能得到的最小累计费用。 1 n == costs.length <= 100000。...问题理解 • 有 n+1 级台阶,编号 0 到 n。 • 数组 costs 长度是 n,下标从 1 开始,costs[i] 表示第 i 级台阶的费用。 • 第 0 级没有费用。...从 i = 3 到 n: • 计算到达 i 的最小费用: • 从 i-3 来:f0 + 9 + costs[i-1] • 从 i-2 来:f1 + 4 + costs[i-1] • 从 i-1 来:f2

    23210

    2022-04-18:things是一个N*3的二维数组,商品有N件,商品编号从1~N, 比如things = , 代表第3号商品:

    2022-04-18:things是一个N*3的二维数组,商品有N件,商品编号从1~N, 比如things3 = 300, 2, 6, 代表第3号商品:价格300,重要度2,它是6号商品的附属商品, 再比如...,它才能被购买, 任何一个附属商品,只会有1个主商品, 任何一个主商品的附属商品数量,不会超过2件, 主商品和附属商品的层级最多有2层。...给定二维数组things、钱数money,返回整体花费不超过money的情况下,最大的收益总和。 答案2022-04-18: 本来想用rust写的,但老是编译不通过,实在没辙。...n } func maxScore(things [][][]int, n, money int) int { dp := make([][]int, n) for i := 0; i n;..., rest int, dp [][]int) int { if rest < 0 { return -1 } if index == n { return 0 } if dp[index

    57420

    Linux操作系统之进程(七):进程的控制(下)

    对于非阻塞循环的返回值,当waitpid的返回大于0时,说明我们等待成功了,它返回的时等待成功的子进程pid,可以退出轮循调用waitpid的循环里了。...如果返回值为0,表示子进程还未返回,我们仍然需要接下来轮循调用waitpid。返回值为-1,表示等待出错误。...倘若等待的返回值大于0,说明等待成功了,我们就可以再把flag更改为false。在下次创建子进程之前,我们的父进程都不会执行waitpid的代码。...接下来,就让我们从最基础的execl开始,来认识一下进程替换的相关函数: int execl(const char *path, const char *arg, ..., NULL); 先不要管函数的参数列表...值得注意,exec系列的函数的返回值情况。如果替换数据与代码成功,自然是不需要返回值的,但如果替换失败了,就会返回-1!

    38510

    有一个整数数组,长度为9,数组里的值是多少不清楚,但是知道数组中有8个值是相等,其中一个小于其他8个值,目前有一个标准函数,compare(int b),返回0相等1大于

    最近做的一个面试题: 有一个整数数组,长度为9,数组里的值是多少不清楚,但是知道数组中有8个值是相等,其中一个小于其他8个值,目前有一个标准函数,compare(int[] a, int[] b),返回...0(相等)、1(大于)、-1(小于),最少调用compare标准函数几次一定能够找出不同的值,请描述具体步骤,并用代码实现,语言不限 思路: 先分成三组 一组三个。...每一组三个数相加,其中有一组和其他两个组不一样,然后范围就缩小到这一组,就三个数,然后可以再两两相加,然后分析这三数之间的大小,调用两次就行 之间上代码(方法虽笨,可以实现,希望有好的方法指教!!)...[]{2,2,2,2,2,2,1,2,2}; int[] a = new int[]{num[0],num[1],num[2]}; int[] b = new int[]...[] h = new int[]{num[0]+num[1]}; int[] i = new int[]{num[1]+num[2]}; int result3

    1.6K10

    每日一练:【优先算法】双指针之移动零(easy)

    一个指针从最左端开始,另一个从最右端开始,然后逐渐往中间逼近。...快慢指针的实现方式有很多种,最常用的一种就是: • 在一次循环中,每次让慢的指针向后移动一位,而快的指针往后移动两位,实现一快一慢。...注:上述双指针是一种抽象的概念,对于像数组的结构,我们是通过记录对应的位置来达成像指针的效果,并不一定是创建指针 1. 题目链接:283....我们创建dest与src指针(效果上的指针,实际上通过[]+下标实现)我们将dest初始化为-1,src初始化为0,通过dest与src的交错,我们就将数组划分成三个部分。...,我们不能直接交换dest与src指向的值,我们先将++dest,dest指向0,src指向非0值,我们再将dest与src指向值交换,再将src++,这样非0值始终在dest指向的左区间,0始终在dest

    75000

    认识一维数组与二维数组

    下表是从0开始的,具体应用请见2.数组的多种初始化 2.数组的多种初始化 首先先来说数组的一种初始化:指在创建的基础上给一个或多个合理的值;而每个类型的初始化又存在差异,本章的初始化我们就来讨论其差异性...,不可能一次性输完,所以要用到循坏语句进行循环输入,讲每个输入的值储存到对应的数组的元素中,直到达到元素值为止。...、二维数组的定义与创建 1.二维数组的定义 如果说一维数组是以数字为元素的集合 如: 1 2 3 4 5 6 7 8 9 10 其中每个元素都是int类型 那二维数组是以一维数组为元素的集合 如 int...printf("%d\n",arr[1][2]); 欸嘿,也许你会认为了,这打印的一定就是1行3列的那个数字 stop!!! stop!!! stop!!! 还记得数组的下标从0开始吗?...(类似于平面x值y值确定一个点,然后给这个点赋值) 同时还需要保证能够输入循坏,保证每一个数组元素都能赋值。所以我们采用循坏的方式进行输入,同理输出也是一个道理。

    1.2K10

    2022-03-18:arr数组长度为n, magic数组长度为m 比如 arr = { 3, 1, 4, 5, 7 },如果完全不改变arr中的值, 那么收益

    2022-03-18:arr数组长度为n, magic数组长度为m 比如 arr = { 3, 1, 4, 5, 7 },如果完全不改变arr中的值, 那么收益就是累加和 = 3 + 1 + 4 + 5...+ 7 = 20 magicsi = {a,b,c} 表示arra~b中的任何一个值都能改成c 并且每一种操作,都可以执行任意次,其中 0 n 那么经过若干次的魔法操作,你当然可能得到...arr的更大的累加和 返回arr尽可能大的累加和 n 的值和c的范围 <= 10^12 答案2022-03-18: 线段树。...return ans } // 为方法三特别定制的线段树 // 区间上维持最大值的线段树 // 支持区间值更新 // 为本道题定制了一个方法: // 假设全是单点查询,请统一返回所有单点的结果(一个结果数组...rt) } func (this *SegmentTree3) buildSingleQuery(n int) []int { ans := make([]int, n+1) this.process

    1.6K30

    2023-11-22:用go语言,给你一个长度为 n 下标从 0 开始的整数数组 nums。 它包含 1 到 n 的所有数字,请

    2023-11-22:用go语言,给你一个长度为 n 下标从 0 开始的整数数组 nums。 它包含 1 到 n 的所有数字,请你返回上升四元组的数目。...大体过程如下: 算法1:countQuadruplets1 1.初始化变量:n为数组长度,ans为结果计数器,dp为动态规划数组。...2.遍历数组,从第二个元素开始(下标为1): a.初始化计数器cnt为0。...算法2:countQuadruplets2 1.初始化变量:n为数组长度,ans为结果计数器,dp为动态规划数组。 2.遍历数组,从第二个元素开始(下标为1): a.初始化计数器cnt为0。...总的时间复杂度:两种算法的时间复杂度都是O(n^2),因为需要两层循环遍历数组。 总的额外空间复杂度:两种算法的空间复杂度都是O(n),因为需要使用一个长度为n的动态规划数组dp。

    90830
    领券