企业官网建设流程全解析

网站建设与管理方案的总结,免费网站制作作业,网上商店网站设计,企业网站建设费计入什么科目2026-01-07#xff1a;查询超过阈值频率最高元素。用go语言#xff0c;给定一个长度为 n 的整数数组 nums 和若干查询 queries#xff0c;queries 中的第 i 项为三元组 [li, ri, thresholdi]#xff08;表示要处理数组区间的左右端点和阈值#xff0c;区间为包含端点的子数…2026-01-07查询超过阈值频率最高元素。用go语言给定一个长度为 n 的整数数组 nums 和若干查询 queriesqueries 中的第 i 项为三元组 [li, ri, thresholdi]表示要处理数组区间的左右端点和阈值区间为包含端点的子数组 nums[li…ri]。对于每个查询要求在指定区间内找出那些出现次数不低于 thresholdi 的元素若存在这样的元素则从中选出出现次数最多的一个如果多个元素出现次数相同则返回数值最小的那个如果没有任何元素满足出现次数不少于 thresholdi则该查询的答案为 -1。最终输出一个结果数组 ans使得 ans[i] 为第 i 个查询的返回值。1 nums.length n 10000。1 nums[i] 1000000000。1 queries.length 5 * 10000。queries[i] [li, ri, thresholdi]。0 li ri n。1 thresholdi ri - li 1。输入 nums [1,1,2,2,1,1], queries [[0,5,4],[0,3,3],[2,3,2]]输出 [1,-1,2]解释查询子数组阈值频率表答案[0, 5, 4][1, 1, 2, 2, 1, 1]41 → 4, 2 → 21[0, 3, 3][1, 1, 2, 2]31 → 2, 2 → 2-1[2, 3, 2][2, 2]22 → 22题目来自力扣3636。 算法分步解析数据预处理值域离散化坐标压缩首先对原始数组nums中的所有元素进行排序和去重得到一个不重复的有序数组a。然后为原数组中的每个元素创建一个映射indexToValue记录其在a中的索引位置。这一步将原本可能很大的整数值最大到 1e9映射到一个紧凑的连续整数范围最大为n即 10000极大地减少了后续计数数组cnt的空间开销。分块大小计算算法根据数组长度n和查询数量m计算出一个合适的块大小blockSize通常为n / sqrt(2*m)。这是莫队算法的关键它将查询排序使左右指针的移动距离尽可能短。查询分类与处理算法根据查询区间的大小采用两种不同的策略小区间暴力处理对于区间长度(r - l 1)小于或等于blockSize的查询直接遍历该区间内的每个元素。使用计数数组cnt统计每个离散化后数值的出现频率并动态维护当前区间的最高频率maxCnt以及达到该频率的最小值minVal。查询结束后检查maxCnt是否满足阈值threshold然后重置计数状态准备处理下一个查询。大区间离线处理莫队算法对于更大的区间算法采用离线处理方式。将所有大查询按照l所在的块编号l / blockSize进行分组同一组内的查询再按右端点r排序。莫队算法处理大查询按块处理算法按块编号顺序处理分组后的查询。右指针移动在处理一个新的块时首先将右指针r重置到当前块的右边界。然后对于该组内的每个查询将右指针从当前位置移动到目标查询的r处并在移动过程中将经过的元素加入计数更新maxCnt和minVal。左指针移动与回滚接着从左指针的起始位置当前块的右边界向左移动至查询的l处添加这些元素并更新状态。此时计数状态反映了整个查询区间[l, r]的信息。在记录答案后左指针需要回退到起始位置并撤销在左移过程中对计数状态的所有修改即“回滚”。这确保了处理下一个查询时计数状态仅包含右指针移动带来的影响保持了处理的正确性。生成答案无论是暴力处理还是莫队算法处理最终都会根据当前查询区间的统计结果判断答案如果maxCnt threshold则答案为minVal否则答案为-1。所有答案被存入结果数组ans并返回。⚙️ 复杂度分析总的时间复杂度算法的总时间复杂度由不同处理方式共同决定离散化预处理排序和创建映射的时间复杂度为O(n log n)。暴力处理小区间最坏情况下所有查询都是小区间每个查询处理时间为 O(区间长度)。总复杂度上限为O(m * blockSize)。莫队算法处理大查询这是性能的关键。在排序后右指针在每个块内整体移动 O(n) 次共有 O(n / blockSize) 个块因此右指针总移动为O(n * (n / blockSize))。左指针在块内因排序而移动总移动次数为O(m * blockSize)。通过设定blockSize n / sqrt(m)可以使总时间复杂度达到平衡约为O(n * sqrt(m))。综上在给定的数据规模下 (n 10000,m 50000)该算法能够高效运行。总的额外空间复杂度算法使用的额外空间主要包括离散化后的数组和映射O(n)。计数数组cntO(n)因为离散化后不同值的数量不超过n。存储查询的结构O(m)。因此总的额外空间复杂度为O(n m)。Go完整代码如下packagemainimport(cmpfmtmathslicessort)funcsubarrayMajority(nums[]int,queries[][]int)[]int{n,m:len(nums),len(queries)a:slices.Clone(nums)slices.Sort(a)aslices.Compact(a)indexToValue:make([]int,n)fori,x:rangenums{indexToValue[i]sort.SearchInts(a,x)}cnt:make([]int,len(a)1)maxCnt,minVal:0,0add:func(iint){v:indexToValue[i]cnt[v]c:cnt[v]x:nums[i]ifcmaxCnt{maxCnt,minValc,x}elseifcmaxCnt{minValmin(minVal,x)}}ans:make([]int,m)blockSize:int(math.Ceil(float64(n)/math.Sqrt(float64(m*2))))typequerystruct{bid,l,r,threshold,qidint}// [l,r) 左闭右开qs:[]query{}fori,q:rangequeries{l,r,threshold:q[0],q[1]1,q[2]// 左闭右开// 大区间离线保证 l 和 r 不在同一个块中ifr-lblockSize{qsappend(qs,query{l/blockSize,l,r,threshold,i})continue}// 小区间暴力forj:l;jr;j{add(j)}ifmaxCntthreshold{ans[i]minVal}else{ans[i]-1}// 重置数据for_,v:rangeindexToValue[l:r]{cnt[v]--}maxCnt0}slices.SortFunc(qs,func(a,b query)int{returncmp.Or(a.bid-b.bid,a.r-b.r)})varrintfori,q:rangeqs{l0:(q.bid1)*blockSizeifi0||q.bidqs[i-1].bid{// 遍历到一个新的块rl0// 右端点移动的起点// 重置数据clear(cnt)maxCnt0}// 右端点从 r 移动到 q.rq.r 不计入for;rq.r;r{add(r)}tmpMaxCnt,tmpMinVal:maxCnt,minVal// 左端点从 l0 移动到 q.ll0 不计入forl:q.l;ll0;l{add(l)}ifmaxCntq.threshold{ans[q.qid]minVal}else{ans[q.qid]-1}// 回滚maxCnt,minValtmpMaxCnt,tmpMinValfor_,v:rangeindexToValue[q.l:l0]{cnt[v]--}}returnans}funcmain(){nums:[]int{1,1,2,2,1,1}queries:[][]int{{0,5,4},{0,3,3},{2,3,2}}result:subarrayMajority(nums,queries)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathfromtypingimportListdefsubarray_majority(nums:List[int],queries:List[List[int]])-List[int]:n,mlen(nums),len(queries)# 坐标压缩asorted(set(nums))index_to_value[0]*nfori,xinenumerate(nums):index_to_value[i]a.index(x)# 这里用 bisect_left 更高效但数据量小可以直接用 indexcnt[0]*(len(a)1)max_cnt,min_val0,0defadd(i:int):nonlocalmax_cnt,min_val vindex_to_value[i]cnt[v]1ccnt[v]xnums[i]ifcmax_cnt:max_cnt,min_valc,xelifcmax_cnt:min_valmin(min_val,x)ans[-1]*m# 计算块大小block_sizeint(math.ceil(n/math.sqrt(m*2)))ifm0else1qs[]# (block_id, l, r, threshold, qid)fori,(ql,qr,threshold)inenumerate(queries):l,rql,qr1# 左闭右开# 大区间离线处理不在同一个块中ifr-lblock_size:qs.append((l//block_size,l,r,threshold,i))continue# 小区间暴力forjinrange(l,r):add(j)ifmax_cntthreshold:ans[i]min_valelse:ans[i]-1# 重置forjinrange(l,r):vindex_to_value[j]cnt[v]-1max_cnt0# 按块排序块内按右端点排序qs.sort(keylambdax:(x[0],x[2]))r0fori,(block_id,ql,qr,threshold,qid)inenumerate(qs):l0(block_id1)*block_sizeifi0orblock_idqs[i-1][0]:# 新的块rl0# 重置cnt[0]*(len(a)1)max_cnt0# 右端点扩展whilerqr:add(r)r1tmp_max_cnt,tmp_min_valmax_cnt,min_val# 左端点扩展forlinrange(ql,l0):add(l)ifmax_cntthreshold:ans[qid]min_valelse:ans[qid]-1# 回滚左端点max_cnt,min_valtmp_max_cnt,tmp_min_valforlinrange(ql,l0):vindex_to_value[l]cnt[v]-1returnans# 测试if__name____main__:nums[1,1,2,2,1,1]queries[[0,5,4],[0,3,3],[2,3,2]]resultsubarray_majority(nums,queries)print(result)C完整代码如下#includeiostream#includevector#includealgorithm#includecmath#includefunctional#includeunordered_mapusingnamespacestd;vectorintsubarrayMajority(vectorintnums,vectorvectorintqueries){intnnums.size();intmqueries.size();// 坐标压缩vectorintsorted_numsnums;sort(sorted_nums.begin(),sorted_nums.end());sorted_nums.erase(unique(sorted_nums.begin(),sorted_nums.end()),sorted_nums.end());unordered_mapint,intvalue_to_index;for(inti0;isorted_nums.size();i){value_to_index[sorted_nums[i]]i;}vectorintindex_to_value(n);for(inti0;in;i){index_to_value[i]value_to_index[nums[i]];}intmax_cnt0,min_val0;// 添加元素到当前窗口autoadd[](inti,vectorintcnt){intvindex_to_value[i];cnt[v];intccnt[v];intxnums[i];if(cmax_cnt){max_cntc;min_valx;}elseif(cmax_cnt){min_valmin(min_val,x);}};vectorintans(m,-1);// 计算块大小intblock_size(m0)?ceil(n/sqrt(m*2)):1;// 定义查询结构体structQuery{intblock_id;intl;intr;intthreshold;intqid;};vectorQueryqs;for(inti0;im;i){intlqueries[i][0];intrqueries[i][1]1;// 左闭右开intthresholdqueries[i][2];// 大区间离线处理不在同一个块中if(r-lblock_size){qs.push_back({l/block_size,l,r,threshold,i});continue;}// 小区间暴力vectorintcnt(sorted_nums.size()1,0);max_cnt0;for(intjl;jr;j){add(j,cnt);}if(max_cntthreshold){ans[i]min_val;}// 不需要显式重置因为 cnt 是局部变量// max_cnt 会在下一轮重置}// 按块排序块内按右端点排序sort(qs.begin(),qs.end(),[](constQuerya,constQueryb){if(a.block_id!b.block_id)returna.block_idb.block_id;returna.rb.r;});intr_ptr0;vectorintcnt(sorted_nums.size()1,0);for(inti0;iqs.size();i){constQueryqqs[i];intl0(q.block_id1)*block_size;if(i0||q.block_idqs[i-1].block_id){// 新的块r_ptrl0;// 重置计数fill(cnt.begin(),cnt.end(),0);max_cnt0;}// 右端点扩展while(r_ptrq.r){add(r_ptr,cnt);r_ptr;}inttmp_max_cntmax_cnt;inttmp_min_valmin_val;// 左端点扩展for(intlq.l;ll0;l){add(l,cnt);}if(max_cntq.threshold){ans[q.qid]min_val;}// 回滚左端点max_cnttmp_max_cnt;min_valtmp_min_val;for(intlq.l;ll0;l){intvindex_to_value[l];cnt[v]--;}}returnans;}intmain(){vectorintnums{1,1,2,2,1,1};vectorvectorintqueries{{0,5,4},{0,3,3},{2,3,2}};vectorintresultsubarrayMajority(nums,queries);for(intx:result){coutx ;}coutendl;return0;}