问题描述 如何求得任意N个整数的最大值与最小值 解决方案 解决这个问题有三种常见思路,第一种思路比较简单粗暴,就是对用户输入的每个整数两两之间进行比较,直到找到最大的整数和最小的整数为止。...第二种思路是将用户输入的整数放入一个空列表中,然后利用Python内置的max()函数和min()函数分别得到最大值和最小值。...第三种思路与第二种思路类似,也是将用户输入的整数放入一个空列表,然后对列表进行排序,列表下标为0的数即为最小值,列表下标为N-1的数即为最大值。...但在我们的实际操作中,用户难免会失误输入错误的数据类型,导致Python无法正常处理某一个或者一段代码的时候就终止运行并出现报错。 如下图: 这时候我们需要对代码进行调整,增强其处理异常数据的能力。...结语 求得任意N个整数的最大值与最小值方法多种多样,其中,将用户输入的整数放入一个空列表,随后对列表进行排序,并增强其处理异常数据的能力使我们的代码更加高效有用!
题目描述 输入一维数组array和n,找出和值为n的任意两个元素。例如: array = [2, 3, 1, 10, 4, 30] n = 31 则结果应该输出1, 30 顺序不重要。...package com.light.sword; /** * @author: Jack * 2021/4/21 下午7:51 * * 输入一维数组array和n,找出和值为n的任意两个元素...(1)第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。 (2)比较第2和第3个数,将小数 放在前面,大数放在后面。......... (3)如此继续,知道比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成 (4)在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的...(5)在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。 (6)依次类推,每一趟比较次数减少依次
#include #define MAX 100001 int a[MAX]; int n; /* 时间复杂度为3*n/2 */ void swap(int i) { if(i...() { int i; for(i=0;i<n;i++) { swap(i); i++; } } int main() { int i,j; scanf("%d",&n); for...(j=0;j<n;j++) scanf("%d",&a[j]); sort(); int min=0,max=0; if(n>1) max=1; i=min;j=max; while(...i<n && j<n) { if(a[min]>a[i]) min=i; if(a[max]<a[j]) max=j; j += 2; i += 2; } if(i<n...) { if(a[n-1]<a[min]) min=n-1; if(a[n-1]>a[max]) max=n-1; } printf("%d %d",a[max],a[min]
vector strs; int separate_characterLen = separate_character.size();//分割字符串的长度...,这样就可以支持如“,,”多字符串的分隔符 int lastPosition = 0,index = -1; while (-1 !...index + separate_characterLen; } string lastString = src.substr(lastPosition);//截取最后一个分隔符后的内容...lastString.empty()) strs.push_back(lastString);//如果最后一个分隔符后还有内容就入队 return strs;
在《算法导论》第一部分练习中,有这样一道算法题: 1.2-3 对于一个运行时间为100n*n的算法,要使其在同一台机器上,在比一个运行时间为2^n的算法运行的很快,n的最小值是多少?...下面给出我自己的解题思路: 对于100n^2和2^n两个算法进行比较,我们可以这样做:对100n^2-2^n操作,如果结果小于0,那么此时的n就是我们所求的值。...100n^2的算法,要使其在同一台机器上,比一个运行时间为2^n的算 8 * 法运行得更快,n的最小值是多少?...2和2^n两个算法进行比较,我们可以这样做:对100n^2-2^n操作,如果结果小于0,那么此时的n就是我们所求的值。...21 * java中求一个数的n次方,方法为Math.pow(x,y);即x的y次方 22 */ 23 public static void getSum() { 24
#include void sort(int*x,int n) { int i,j,k,t; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j+...numbers:"); for(i=0;i<10;i++) scanf("%d",p++); p=a; sort(p,10); for(;p<a+10;p++) { printf("%d\n"
我是川川,有问题留言or加我扣扣私聊:2835809579 原题: 定义一个函数int isprime(int n),用来判别一个正整数n是否为素数。...在主函数中输入两个正整数m和n(m>=1,n>m),统计并输出m和n之间的素数的个数以及这些素数的和。...输入输出示例 输入:2 10 输出:count = 4 ,sum = 17 代码: 在这里插入代码片 ```c #include int isprime(int n) { int i=2;...for(i;i<n;i++) { if(n%i==0) break; } if(i==n) return 1;...else return 0; } int main() { int m,n,count=0; int sum=0; scanf("%d %d",&m,&n);
本节,我们就来探讨如何解决这两个问题。 求前K个最大的元素 基本思路 一个简单的思路是排序,排序后取最大的K个就可以了,排序可以使用Arrays.sort()方法,效率为O(N*log2(N))。...另一个简单的思路是选择,循环选择K次,每次从剩下的元素中选择最大值,这个效率为O(N*K),如果K的值大于log2(N),这个就不如完全排序了。...一个基本的思路是维护一个长度为K的数组,最前面的K个元素就是目前最大的K个元素,以后每来一个新元素的时候,都先找数组中的最小值,将新元素与最小值相比,如果小于最小值,则什么都不用变,如果大于最小值,则将最小值替换为新元素...这样,数组中维护的永远是最大的K个元素,而且不管源数据有多少,需要的内存开销是固定的,就是长度为K的数组。不过,每来一个元素,都需要找最小值,都需要进行K次比较,能不能减少比较次数呢?...一个简单的思路是排序,排序后取中间那个值就可以了,排序可以使用Arrays.sort()方法,效率为O(N*log2(N))。 不过,这要求所有元素都是已知的,而不是动态添加的。
By CaesarChang 合作: root121toor@gmail.com ~关注我 带你看更多精品知识 见注释 简单动态规划问题 将前面的数之和做一个更新...Solution { public int maxSubArray(int[] nums) { int Max=nums[0]; int pre=0; //记录前面的和...int cur=0; //记录当前数 for(int num:nums){ cur=num; if(pre>0){ //如果前面的和>...0,当前数字+前面的和 cur+=pre; } if(cur>Max){ Max=cur;...} pre=cur; //更新前面的和 } return Max; } } ?
2021-07-27:给定一个数组arr,长度为N,arr中的值只有1,2,3三种。...arri == 1,代表汉诺塔问题中,从上往下第i个圆盘目前在左;arri == 2,代表汉诺塔问题中,从上往下第i个圆盘目前在中;arri == 3,代表汉诺塔问题中,从上往下第i个圆盘目前在右。...那么arr整体就代表汉诺塔游戏过程中的一个状况。如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1。如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况。...福大大 答案2021-07-27: 1-7的汉诺塔问题。 1-6左→中。 7左→右。 1-6中→右。 单决策递归。 k层汉诺塔问题,是2的k次方-1步。 时间复杂度:O(N)。...空间复杂度:O(1)。 代码用golang编写。
思路:这种题目属于基础的笛卡尔树的题目,但是这里我们换一种方式论述。 由于所有的值都是正整数,所以区间长度在最小值不变的情况下越大越好。 我们把这个数组按照最小值进行划分。...容易知道如果把当前的最小值作为答案区间的最小值, 取整个数组的话答案一定最大, 所以此时就可以用最小值和整个数组的和更新一次答案。...我们惊讶的发现这就是一个递归求解的问题。 由于每一次分割都会少一个值, 可以发现计算的次数就是数组长度。 现在只有最后一个问题:找到最小值所在的位置。...前缀和+单调栈 经典单调栈题目。因为数组元素都为正数,所以子数组最小值的元素位置一定时,子数组长度越大,得到的乘积越大。...我们利用单调栈可以求出每个元素作为最小值时的最长子数组,再利用预计算的前缀和求得乘积。最后取所有乘积的最大值即可。 时间复杂度\mathcal{O}(N)O(N)。
2022-10-05:在一个 n x n 的整数矩阵 grid 中,每一个方格的值 gridi 表示位置 (i, j) 的平台高度。当开始下雨时,在时间为 t 时,水池中的水位为 t 。...你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的。当然,在你游泳的时候你必须待在坐标方格里面。...你从坐标方格的左上平台 (0,0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。...时间复杂度:O(N*2logN)。空间复杂度:O(N**2)。代码用rust编写。...let mut visited: Vec> = repeat(repeat(false).take(m as usize).collect()) .take(n
这样,我们可以使用二分查找算法在 O(log n) 的时间内找到最大值,并进行交换操作。...假设我们有一个大小为n的堆,我们可以通过以下步骤进行MAX-HEAPIFY操作: 1.从最后一个非叶子结点(即第n/2个结点)开始向上遍历,找到最小值。 2.将该最小值与当前根结点交换。...另一方面,由于堆的大小为 n,因此我们可以通过直接返回堆的最大值,来计算从根节点到叶节点路径上的每个节点的最大值。这种方法的时间复杂度为 O(n)。...因此,路径的长度从 1 到 log2(n)。 现在,让我们来考虑 MAX-HEAPIFY 在这种堆中的运行情况。...在我们构造的堆中,从根节点到每个叶节点的路径长度在 1 到 log2(n) 之间,因此 MAX-HEAPIFY 的最坏情况运行时间为 O(log2(n))。
在长度为N的数组中,如果次数与N的大小无关,始终为一个固定的次数,或许是1次,或许是3次,它们都记为O(1),也叫常数阶,一个遍历就是O(N),也叫线性阶,嵌套两个遍历就是 O(N^2),也叫平方阶,...如果有二分分治,那就是O(log2^N) 。 如果一个遍历嵌套一个二分,则是O(N*log2^N)。 空间复杂度 空间复杂度是指算法在执行过程中临时占用内存的量度,空间复杂度仍旧使用大写字母O来表示。...个新的临时空间,排序比较又要占用log2^N ,所以完整的空间复杂度为O(n*log2^n)。...再说一下堆的特性 在一个长度为N的堆中,位置k的节点的父节点的位置为k/2,它的两个子节点的位置分别为2k和2k+1,该堆总共有N/2个父节点。...时间复杂度:基数排序的时间复杂度计算比较复杂,我们通过代码进行分析,首先是按照最大位数进行循环,这个最大位数很难去定义,它不是数组的长度N,而是要找出最大值然后判断最大值的位数,这是与N无关的,例如数组
这是因为在最坏情况下,每次分区操作都会将数组分成大小相等的两部分,因此每次都需要从剩下的 n-1 个元素中随机选择一个元素作为主元。...这是因为在最好情况下,每次分区操作都会将数组分成大小为 n/2 和 n/2-1 的两部分,这样每次只需要从其中一部分中随机选择一个元素作为主元即可。...在最好情况下,每次递归调用 quicksort() 函数时会使用数组中的一个元素作为随机数,此时 random() 被调用的次数为 n 次。...这是因为在随机选择基准值时,有可能第一次选择的基准值就是排序数组中的最小值或最大值,这样就不需要再次调用 RANDOM 函数了。...如果第一次选择的基准值不是最小值或最大值,那么需要再次调用 RANDOM 函数来生成一个新的随机数。
(3)O(n):线性阶,如n个数内找最大值 (4)O(nlogn):对数阶,如快速排序算法 (5)O(n^2):平方阶,如选择排序,冒泡排序 (6)O(n^3):立方阶,如两个n阶矩阵的乘法运算 (7...; n = 2^k; k则是以2为底,n的对数,就是Log2N; 那么二分查找的时间复杂度就是O(Log2N); (3)O(n):线性阶,如n个数内找最大值。...操作的数量与输入数据的规模 n 成正比。n = 10,000 -> 5000 operations 这一类算法中操作次数和n正比线性增长。...(4)O(nlogn):对数阶,如快速排序算法 上面看了二分查找,是LogN的(LogN没写底数默认就是Log2N); 线性对数阶就是在LogN的基础上多了一个线性阶; 比如这么一个算法流程: 数组...a和b,a的规模为n,遍历的同时对b进行二分查找,如下代码: for(int i =0;i<n;i++) { binary_search(b); } (5)O(n^2):平方阶,如选择排序,冒泡排序
: 随着n值变大,5n2+7n和3n2+2n,执行曲线重合,说明这种情况下,5和3可以忽略。...对数阶O(log2n)int i = 1;while(i<n){ i*=2;}说明:在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了。...假设循环x次之后,i就大于2了,此时这个循环就退出了,也就是说2的x次方等于n,那么x=log2n也就是说当循环log2n次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(log2n)。..."); System.out.println(Arrays.toString(arr)); }}小结冒泡排序规则(1)一共进行数组的大小-1次大的循环(2)每一趟排序的次数在逐渐的减少...它的基本思想是:第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1]arr[n-1]中选取最小值,与arr[1]交换,第三次从arr[2]~arr[n-1]中选取最小值
# 题目链接 # 双指针 我们有k升序排列的整数数组,先思考如何找到一个包含列表中至少一个数的区间?...我们使用k个指针分别指向列表的开始元素,每次遍历这k个元素,找到其中最大最小值,如果当前区间较小,就更新答案,然后将指向最小值元素的指针加上1,表示将后面的元素加入到区间中。...) 空间复杂度:O(k)O(k)O(k) # 双指针+堆 我们不用每次都遍历k个指针,可以将这k个指针所指元素放入到小顶堆中,每次从堆中弹出这个元素,得到最小值,同时用一个变量维护保存最大值即可。...nklog2k)O(nklog_2k)O(nklog2k),n是k个列表的平均长度,出堆操作需要O(log2k)O(log_2k)O(log2k),最坏情况下,每个指针都可能从头走到尾,因此时间复杂度为...O(k∗n∗log2k)O(k*n*log_2k)O(k∗n∗log2k) 空间复杂度:O(k)O(k)O(k)
堆排序 ---- 堆Heap 堆是一个完全二叉树 每个非叶子结点都要大于或者等于其左右孩子结点的值称为大顶堆 每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆 根结点一定是大顶堆中的最大值,一定是小顶堆中的最小值...大顶堆 完全二叉树的每个非叶子结点都要大于或者等于其左右孩子结点的值称为大顶堆 根结点一定是大顶堆中的最大值 小顶堆 完全二叉树的每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆 根结点一定是小顶堆中的最小值...] 2、构建大顶堆——核心算法 度数为2的结点A,如果它的左右孩子结点的最大值比它大的,将这个最大值和该结点交换 度数为1的结点A,如果它的左孩子的值大于它,则交换 如果结点A被交换到新的位置,还需要和其孩子结点重复上面的过程...从起始结点开始向左找其同层结点,到头后再从上一层的最右边结点开始继续向左逐个查找,直至根结点 2.3 大顶堆的目标 确保每个结点的都比左右结点的值大 3、排序 将大顶堆根结点这个最大值和最后一个叶子结点交换...,那么最后一个叶子结点就是最大值,将这个叶子结点排除在待排序结点之外 从根结点开始(新的根结点),重新调整为大顶堆后,重复上一步 图片摘自Wiki ?
堆排序中建堆过程的时间复杂度O(n) 快速选择 时间复杂度是o(n) 每日一题:堆排序中建堆过程的时间复杂度是 查缺补漏 时间复杂度 定义: 若有某个辅助函数f(n), 使得当n趋近于无穷大时, 敲黑板.../2)n^2+(1/2)n)+1 即O(n^2) 应用 堆排序中建堆过程的时间复杂度O(n) 其实,建堆的整个过程中一个节点的比较次数是与它的高度k成正比的, 所以,我们可以得出 第h层的元素有...如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素 ** 如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素?...* 第一次分区查找,我们需要对大小为 n 的数组执行分区操作,需要遍历 n 个元素。 * * 第二次分区查找,我们只需要对大小为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。...* 如果我们把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1 * 这是一个等比数列求和, * * 最后的和等于 2n-1。
领取专属 10元无门槛券
手把手带您无忧上云