一个数组[1..n]的某些有序类型的元素(即x <y总是被定义),我想使用"分而治之"算法找到数组中的最小值.
这项任务到底意味着什么？
您将获得2010年奥运会门票的数量A. 该数组在请求时被排序,因此A(1)是第一个到达而A(2)是第二个到达等.每个请求包含一个十位数的电话号码.为了公平起见,奥运会组织者规定每个电话号码只能有一个请求.已经注意到,阵列A包含来自某些电话号码的多个请求.写一个O(nlogn)时间除法和征服算法,从A中删除来自同一电话号码的所有请求,除了第一次收到的请求.最终输出应该是阵列A,其中包含来自唯一电话号码的m <= n个请求.此外,A中的请求应保持与删除重复之前的顺序相同.
如果数组按电话号码排序,我知道如何做到这一点但是我不知道当数组按请求时间排序时是如何实现的.
仍然掌握对数与指数的对立面.(将它们描述为指数的反转也是正确的吗？)
Big-O符号上已经有很多很棒的SO条目,包括O(log n)和QuickSort n(log n).找到了一些有用的图表.
在看Divide and Conquer算法时,我遇到了n log n,我认为这个算法n乘以它的值log n.我经常尝试100 log 100这样的具体例子,以帮助可视化抽象方程式中发生的事情.
只是阅读log n假设base 10.是否n log n翻译成:
"数量n乘以10的数量需要提高到等于n的数量"？
所以100 log 100相等,200因为10需要被提升到2的幂,等于100？
当算法迭代一组时,基数是否会发生变化？如果我们正在谈论抽象,那么基数是否重要？
我正在与一位同学争论,因为他想说服我,有可能在不使用递归的情况下实现分而治之的算法.
这是真的吗？
我无法在我的"多数元素"上获得正确的输出,并在Python 3中征服算法实现.
这应该是相对正确的; 但是,我似乎仍然缺少一些东西,或者它稍微偏了,我无法弄清楚为什么会这样.
我尝试了一些调试语句和不同的东西.它看起来像在代码上面的注释中列出的特定情况,它为"left_m"解析-1,在执行递归调用时解析为"right_m"的941795895.当它将每个索引处的元素与这些变量进行比较时,计数器显然永远不会递增.
我是以错误的方式来做这件事的吗？任何帮助将不胜感激.
谢谢.
# Input:
# 10
# 2 124554847 2 941795895 2 2 2 2 792755190 756617003
# Your output:
# 0
#
# Correct output:
# 1
def get_majority_element(a, left, right):
if left == right:
return -1
if left + 1 == right:
return a[left]
left_m = get_majority_element(a, left, (left + right - 1)//2)
right_m = get_majority_element(a, (left + right - 1)//2 + 1, right)
left_count = 0
for i in range(0, right):
if …我需要创建一个算法，该算法采用数组A作为参数，并找到A的一个子数组，其元素之和乘以该子数组中的最小元素会产生最大值。A中的值为正数，我们无法更改该数组中的顺序。
有人告诉我可以在 O(nlogn) 内完成。我正在考虑某种分而治之的算法来服从暴力方法。
有任何想法吗？
我需要有关如何获得某个数字的第n个根的帮助.
用户输入他想要root的数字n和数字.我需要在没有cmath lib和分而治之的方法下解决这个问题.
这是我的代码还没有工作:
#include<iostream>
using namespace std;
float pow(float a,float c){
if (a == 0)
return 0;
else if(a == 1)
return 1;
else{
float p = pow(a,(c/2));
if(c%2)
return p*p*a;
else
return p*p;
}
}
int main(){
float a,b;
float c;
cout << "Enter positive number:(base)" << endl;
do{
cin >> a;
}while (a < 0);
cout << "Enter number: (root)" << endl;
cin >> b;
c = 1/b;
cout << "Result:"<<pow(a,c) << endl;
system("pause");
return 0;
} …我一直认为迭代搜索是在未排序列表中查找最大值的首选方法.
这个想法相当随机,但简而言之:我相信我可以在O(logn)时间内完成任务,n是输入数组的大小.
合并排序的方法:分而治之.
步骤1:将findMax()任务划分为两个子任务findMax(leftHalf)和findMax(rightHalf).这个部门应该及时完成O(logn).
第2步:合并两个最大候选人备份.该步骤中的每个层应该花费恒定的时间这是错的.每次比较都是在恒定时间内完成的,但是还有O(1),并且在前一步骤中存在O(logn)这样的层.所以它也应该及时完成O(1) * O(logn) = O(logn)(原谅滥用符号).2^j/2这样的比较(第j级的2 ^ j对候选者).
因此,整个任务应该及时完成O(logn).O(n)时间.
但是,当我尝试计时时,我会得到清晰反映线性O(n)运行时间的结果.
size = 100000000 max = 0 time = 556
size = 200000000 max = 0 time = 1087
size = 300000000 max = 0 time = 1648
size = 400000000 max = 0 time = 1990
size = 500000000 max = 0 time = 2190 …
描述:
给定两个排序的数组(非下降),在T = O(lg(m + n))中找到Kth min元素,m和n分别是两个数组的长度.
问题:
不了解下面的算法大约有三点:
代码: Java.解决方案:二进制搜索.
// k is based on 1, not 0.
public int findKthMin(int[] A, int as, int ae,
int[] B, int bs, int be, int k) {
int aLen = ae - as + 1;
int bLen = be - bs + 1;
// Guarantee the first array's size is smaller than the second one,
// which is convenient to remaining part …对于数组中的分而治之算法，我们需要能够找到范围的中间元素。显而易见的方法是mid = (leftSide + rightSide) / 2。但是，我听说这种方式不正确，我们需要改为编写mid = leftSide + (rightSide - leftSide) / 2。有人能解释一下这两者之间的区别吗？