在我学习算法设计的过程中,我开始练习一些问题,我很难找到一个有效的解决方案。
给出一个整数数组A,求出在Ai <= Aj约束下j-i的最大值.A:3 5 4 2输出:2对(3,4)
def maxIndex(arr):
max_val = float("-inf")
for i in range(0,len(arr)):
for j in range(i + 1 , len(arr)):
#print(arr[i],arr[j])
if arr[i] <= arr[j]:
diff_i = j - i
我正试图从谦卑中解决一个问题,我已经有了解决办法。问题描述如下,
A non-empty array A consisting of N integers is given.
A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]
我必须写下算法的大O符号,我必须为我的家庭作业想出一个算法。
我可以断定下面的代码是O(n^2)。因为对于每个x,我必须遍历所有的y,并且随着世界的变大,它变得更慢。
int[][] world = new world[20][20];
for (int x = 0; x < 20; x++)
{
for (int y = 0; y < 20; y++)
{
..
}
}
但是,对于另一个问题,我必须遍历世界的下半部分,所以我的y循环减少了一半。
int[][] world = new world[20][20];
for (int x =
在一次技术面试中,这个无理取闹的人向我走来。我谨慎地写了这篇文章。
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("enter size of the array: ");
if (!in.hasNextInt()) {
System.out.println("put an integer! ");
}
int
我必须遵循的复杂度是o(n),所以我不允许使用嵌套循环。我大概知道我想做什么,但是我不确定如何存储范围的下限。目标是找到包含最多元素的区间的下界。我们将L表示为范围的长度。我试过的是:
lst = [1,2,3,4,5,5,6,6,6,12] #after sorting by radix
L = 3
for i in range(len(lst)):
lower_bound[i] = i
upper_bound[i] = i + L #in this case L = 3.
#if i is in range of certain i and its uppe
首先- yes,我在这里读过几篇文章,以及关于估计算法复杂性的其他地方。
我读过,和,以及其他书
我想试着用我写的一个算法来找出最大的矩形,看看我是否从我所读到的东西中完全理解了任何东西。
public static long getLargestRectangle(long[] arr, int index, long max) {
int count = 1; //1 step * 1
int i = index - 1; //1 step * 1
int j = index + 1; /
在使用CompareToAll方法实现数组中的get Max number时,增强了不将每个数字与其他数字进行比较,而是仅将每个数字与之后出现的数字进行比较。本质上,当前数字之前的每个数字都已经与当前数字进行了比较。因此,如果只与当前数字之后的数字进行比较,则该算法仍然是正确的。现在我明白了为什么最坏的运行时间是O(n2) O("n平方“),但我不能理解的是为什么最快的运行时间是O(1)。
我想在最好的情况下它应该等于O(n)
我正在实现一个名为IntegralImage的类,它有一个2D数组作为实例变量。2D数组表示一个图像,其高度为第一个索引,宽度为第二个索引。下面的代码是否在O(n)时间内构造二维数组,n是像素数(高度*宽度)?此外,我也不明白什么是确切的内存使用,以及如何确定它。我必须使用O(n)内存构造数组。
private final int[][] integralImage;
private final int imageHeight; // height of image (first index)
private final int imageWidth; // width of image (s
我有一个满是数字的数组。我需要找到两个数字之间的最大差异,但最大的数字在数组中最小的数字之前。
public static int maximalDrop (int [] a)
例如:
对于数组5、21、3、27、12、24、7、6、4,结果为23 (27-4)。
对于数组5、21、3、22、12、7、26、14,结果为18 (21-3)。
我的解决方案是取数组中的第一个元素(这个数字很大),检查这个数字和数组中所有其他数字之间的差异,然后做同样的事情,但是与数组中的下一个数字进行比较,当然,比较差异并返回最大的一个。我认为我的解决方案是O(n平方),所以我可以少做一点吗?
我想知道是否有更好的方法或惯用的方法来计算数组中的最大int值,并且比O(nlogn)更快?
这段代码给出了O(n),但我觉得它太长了
fun countMax(n: Int, ar: Array<Int>): Int {
val max = ar.max();
var countMax = 0
for(i in ar)
if(i==max)
countMax++
return countMax
}
fun main(args: Array<String>) {
v
我有许多未排序数字的列表,例如:
N=1000000
x = [random.randint(0,N) for i in range(N)]
我只想要顶部k个最小值,目前这是我的方法。
def f1(x,k): # O(nlogn)
return sorted(x)[:k]
这会执行大量的冗余操作,因为我们也在对剩余的N元素进行排序。枚举也不起作用:
def f2(x,k): # O(nlogn)
y = []
for idx,val in enumerate( sorted(x) ):
if idx == k: break
y.appe
我想从10个数字中找出三个最大的数字(区域),我写了这段代码,但是只有最大的数字是正确的,第二和第三大数字是错误的。所以我需要帮助。有什么建议吗?圣诞快乐!
#include <stdio.h>
#define N 3
int main()
{
int i,j;
int area;
int maxArea[N];
int empty = N;
for(j=0;j<10;j=j+1)
{
printf("Input:");
s