关键词:
2021-08-26:长度为N的数组arr,一定可以组成N^2个数字对。例如arr = [3,1,2],数字对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2),也就是任意两个数都可以,而且自己和自己也算数字对,数字对怎么排序?第一维数据从小到大;第一维数据一样的,第二维数组也从小到大,所以上面的数值对排序的结果为:(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)。给定一个数组arr,和整数k,返回第k小的数值对。
福大大 答案2021-08-26:
1.暴力解。
时间复杂度:(N^2 * log(N^2)).
2.下标定位+bfprt算法。
2.1.k–。
2.2.定位下标i1和i2。
i1=k/N。
i2=k%N。
2.3.根据bfprt算法求出第i1小和第i2小的数。
时间复杂度:O(N)。
空间复杂度:O(1)。arr数组里的元素顺序会发生变化。
代码用golang编写。代码如下:
package main
import (
"fmt"
"math/rand"
)
func main()
arr := []int1, 2, 3
k := 4
ret := kthMinPair3(arr, k)
fmt.Println(ret)
// O(N)的复杂度,你肯定蒙了
func kthMinPair3(arr []int, k int) []int
N := len(arr)
if k > N*N
return nil
// 在无序数组中,找到第K小的数,返回值
// 第K小,以1作为开始
fristNum := getMinKth(arr, (k-1)/N)
// 第1维数字
lessFristNumSize := 0
fristNumSize := 0
for i := 0; i < N; i++
if arr[i] < fristNum
lessFristNumSize++
if arr[i] == fristNum
fristNumSize++
rest := k - (lessFristNumSize * N)
return []intfristNum, getMinKth(arr, (rest-1)/fristNumSize)
// 改写快排,时间复杂度O(N)
// 在无序数组arr中,找到,如果排序的话,arr[index]的数是什么?
func getMinKth(arr []int, index int) int
L := 0
R := len(arr) - 1
pivot := 0
var range2 []int
for L < R
pivot = arr[L+rand.Intn(R-L+1)]
range2 = partition(arr, L, R, pivot)
if index < range2[0]
R = range2[0] - 1
else if index > range2[1]
L = range2[1] + 1
else
return pivot
return arr[L]
func partition(arr []int, L int, R int, pivot int) []int
less := L - 1
more := R + 1
cur := L
for cur < more
if arr[cur] < pivot
less++
arr[less], arr[cur] = arr[cur], arr[less]
cur++
else if arr[cur] > pivot
arr[cur], arr[more] = arr[more], arr[cur]
more--
else
cur++
return []intless + 1, more - 1
执行结果如下:
未排序数组中累加和为给定值的最长子数组长度(代码片段)
未排序数组中累加和为给定值的最长子数组长度描述给定一个无序数组arr,其中元素可正、可负、可0。给定一个整数k,求arr所有子数组中累加和为k的最长子数组长度输入描述:第一行两个整数N,k。N表示数组长度,k的... 查看详情
2023-01-06:给定一个只由小写字母组成的字符串str,长度为n,给定一个只由01组成的数组arr,长度为n,arr[i]==0表示str中i位置的字符不许修改,arr[i]==(代码片段)
...23-01-06:给定一个只由小写字母组成的字符串str,长度为N,给定一个只由0、1组成的数组arr,长度为N,arr[i]等于0表示str中i位置的字符不许修改,arr[i]等于1表示str中i位置的字符允许修改,给定一个正数... 查看详情
2021-08-03:完美洗牌问题。给定一个长度为偶数的数组arr,假设长度为n*2,左部分:arr[l1……ln],右部分:arr[r1……rn],请把arr调整成arr[l1,r1,l2,r2,(
2021-08-03:完美洗牌问题。给定一个长度为偶数的数组arr,假设长度为N*2,左部分:arr[L1……Ln],右部分:arr[R1……Rn],请把arr调整成arr[L1,R1,L2,R2,L3,R3,…,Ln,Rn]。要求:时间复杂度O(N),额外空间... 查看详情
2022-05-20:给定一个正数数组arr,长度为n,依次代表n个任务的难度,给定一个正数k,你只能从0任务开始,依次处理到n-1号任务结束,就是一定要从左往右处理任务,只不过,难度差距绝对值不(代
2022-05-20:给定一个正数数组arr,长度为N,依次代表N个任务的难度,给定一个正数k,你只能从0任务开始,依次处理到N-1号任务结束,就是一定要从左往右处理任务,只不过,难度差距绝对值不... 查看详情
2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组,求剩下的数组,严格连续递增的子数组最大长度。n<=10^6。来自字节。5.6笔试。(代码片段)
2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组,求剩下的数组,严格连续递增的子数组最大长度。n<=10^6。来自字节。5.6笔试。答案2022-08-22:动态规划+线段树。代码用rust编写... 查看详情
python数组求和
...返回结果仍是二维矩阵。#定义函数,arr为数组,n为数组长度,可作为备用参数,这里没有用到。def _sum(arr,n): #使用内置的sum函数计算。return(sum(arr)) #调用函数arr=[] #数组元素arr = [12, 3, 4, 15]... 查看详情
在线性时间内查找长度为 N、数字 1 到 N-1 的数组中的重复项,而无需使用额外的 obj/arr 来跟踪计数
】在线性时间内查找长度为N、数字1到N-1的数组中的重复项,而无需使用额外的obj/arr来跟踪计数【英文标题】:Find,inlineartime,duplicateinarrayoflengthN,numbers1toN-1withoutusingadditionalobj/arrtokeeptrackofacount【发布时间】:2021-08-2114:58:28【问题... 查看详情
2022-08-06:给定一个数组arr,长度为n,arr中所有的值都在1~k范围上,你可以删除数字,目的是让arr的最长递增子序列长度小于k。返回至少删除几个数字能达到目的。n<=10^4(代码片段
2022-08-06:给定一个数组arr,长度为N,arr中所有的值都在1~K范围上,你可以删除数字,目的是让arr的最长递增子序列长度小于K。返回至少删除几个数字能达到目的。N<=10^4,K<=10^2。来自京东。4.2... 查看详情
给定一个长度为 n 的数组,找到子集的 XOR 等于给定数字的子集数
】给定一个长度为n的数组,找到子集的XOR等于给定数字的子集数【英文标题】:Givenanarrayoflengthn,findnumberofsubsetswhereXORofasubsetisequaltoagivennumber[closed]【发布时间】:2015-12-0805:34:39【问题描述】:给定一个长度为n的数组arr,找出有... 查看详情
给定一个长度为 n 的数组,找到子集的 XOR 等于给定数字的子集数
】给定一个长度为n的数组,找到子集的XOR等于给定数字的子集数【英文标题】:Givenanarrayoflengthn,findnumberofsubsetswhereXORofasubsetisequaltoagivennumber[closed]【发布时间】:2015-12-0805:34:39【问题描述】:给定一个长度为n的数组arr,找出有... 查看详情
"codinginterviewguide"--在数组中找到一个局部最小的位置(代码片段)
【题目】 定义局部最小的概念:arr长度为1时,arr[0]是局部最小;arr的长度为N(N>1)时,如果arr[0]<arr[1],那么arr[0]是局部最小,如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小;如果0<i<N-1,既有arr[i]<arr[i-1],又有arr[i]<ar... 查看详情
局部最小值位置
定义局部最小的概念。arr长度为1时,arr[0]是局部最小。arr的长度为N(N>1)时,如果arr[0]<arr[1],那么arr[0]是局部最小;如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小;如果0<i<N-1,既有arr[i]<arr[i-1]又有arr[i]<arr[i+1],那么ar... 查看详情
2021-12-26:给定一个长度为n的数组arr,求有多少个子数组满足:子数组两端的值,是这个子数组的最小值和次小值,最小值和次小值谁在最左和最右无所谓。n<=100000(10^5)n*((代码片
2021-12-26:给定一个长度为n的数组arr,求有多少个子数组满足:子数组两端的值,是这个子数组的最小值和次小值,最小值和次小值谁在最左和最右无所谓。n<=100000(10^5)n*lognO(N)。来自腾讯。答案2021-1... 查看详情
golang堆排序(代码片段)
...quot;---")fmt.Println(arr)//堆排序funcheapSort(arr[]int)//求数组长度//根据堆的规律,假设子节点的规律,假设子节点的坐标为i//左子节点坐标为2i+1,右子节点坐标为2i+2//父节点的坐标为(i-1)/2.此处可以计算无论最后一位数字在做左... 查看详情
2022-07-27:小红拿到了一个长度为n的数组arr,她准备只进行一次修改,可以将数组中任意一个数arr[i],修改为不大于p的正数(修改后的数必须和原数不同),并使得所有数之和为x的倍数。(代码
2022-07-27:小红拿到了一个长度为N的数组arr,她准备只进行一次修改,可以将数组中任意一个数arr[i],修改为不大于P的正数(修改后的数必须和原数不同),并使得所有数之和为X的倍数。小红想知道,... 查看详情
8.最大滑动窗口问题(代码片段)
...5,4,3,3,6,7],当窗口w大小为3时,滑动过程如下图:如果数组长度为n,窗口大小为w,则一共产生n-w+1个窗口最大值,请实现一个函数。分析: 本题可以用一个双端队列queue来模拟一个窗口,queue中存储数组值对应的下标,则实现... 查看详情
go笔记:切片(代码片段)
切片是对数组的拓展,在Go中数组的长度一旦定义无法被修改,切片的长度是不固定的,可以理解为切片是一个可变长度数组,是一个有相同类型元素的可变长度序列。1、声明切片1.1、显示声明切片1、语法 声明切片语... 查看详情
数字问题4:在两个长度相等的数组中找上位数(代码片段)
给定两个有序数组arr1和arr2,已知两个数组的长度都为N,求两个数组中所有数的上中位数。上中位数:假设递增序列长度为n,若n为奇数,则上中位数为第n/2+1个数;否则为第n/2个数[要求]时间复杂度为O(... 查看详情