试着做一些练习,我跑过这个问题......
给定两个int数组A和B,以及一个int c,返回对的总数(a,b),其中a来自A,b来自B,a + b是<= c
立即想出了蛮力解决方案,但似乎无法连接点以便在更好的时间复杂性中做到这一点.我首先尝试对数组进行排序,并尝试找到某种类型的模式,但这并没有让我任何地方.我想过一个数组有负数的情况.在这种情况下,我不能只查看A或B中的值并检查它本身是否小于c,因为在另一个数组中可能存在负值,当它们加在一起时会得到<= c的结果.任何见解,想法或线索将不胜感激.
import java.util.*;
public class CountPairs {
public static void main(String args[]){
int arrayA[] = {32,45,9,4};
int arrayB[] = {43,457,54,90};
Scanner scan = new Scanner(System.in);
System.out.println("Choose the value that you want to find pairs <= ");
int c = scan.nextInt();
System.out.println("The total number of pairs are : " + pairs(arrayA, arrayB, c));
}
public static int pairs(int A[], int B[], int n) {
int count = 0;
for (int i = 0; i …因此,我遇到了使用getRandomElement()函数构建集合的问题.乍一看很容易.但是我想的越多,我认为在O(1)时间复杂度中做到这一点的可能性越小.没有给出恒定时间的要求,但所有一组主要功能都是在恒定的时间内,所以我觉得它暗示这也应该在恒定时间内完成.
集合的目标是使用散列函数来减少冲突.问题现在变成,如果你只是生成随机整数并尝试使用这个随机整数选择索引,你很可能会遇到你的集合中的"空"插槽....在这种情况下你必须生成一个新的随机数然后再试一次.基本上你的散列函数越好,你的getRandomElement将使用这种方法执行的最差.
那么我想......好吧,为什么不在每次插入后存储索引？然后,生成一个随机数并从该索引集合中选择一个索引.我认为这是一个好主意,但后来出现了删除元素的问题.我们还必须从索引列表中删除相应的索引,以及从我们的Set中删除元素本身.我们怎样才能找到正确的索引来删除比线性时间更快的???
无论如何,从一组FEELS中获取一个随机元素就可以比线性时间更好.顺便说一下,我正在通过链接来处理碰撞.我不想浪费时间去做数学上不可能的事情,但我也不是数学家,我不想放弃实际可行的事情.
我遇到了一个类似的问题 Given a million integers, return the kth smallest element。问题下方有一个给定的解决方案，我不确定为什么这是最佳解决方案。给定的解决方案涉及使用最小堆。所以最初，我认为这是有道理的，因为我们可以在恒定时间内找到堆中的最小元素。但在我再思考一秒钟后，我想到了将数组中的元素插入堆中的成本。如果我的理解是正确的，插入是一种O(logN)操作。但是如果我们插入N元素，那么这应该花费我们O(NlogN)时间。我们还为我们正在使用的堆使用了额外的空间。所以我的问题是，为什么这比对数组进行排序并取第 k-1 个索引更好的解决方案？
我正在尝试将列表分成尽可能大的子列表。如果列表不能以这种方式划分，我将根据需要进行处理，但是我需要获得除N本身以外的最大数目，该数目将N均分。
我写了一个非常幼稚的解决方案，但是我觉得应该有一个公式或某种东西可以在恒定时间内做到这一点。我的列表不是很大，最大大小为1000。这可能不是关键路径，但是有更好的算法吗？
public static int largestDivisor(int n){
int divisor = 0;
for (int i = 1; i <= n/2; i++)
if (n % i == 0)
divisor = i;
return divisor;
}
我想知道在C中有没有办法提示用户输入2个不同的值,然后分别存储这两个值,所有这些都在一个用户条目中.例如:
Enter your age and blood type : 34 AB
然后我们分别存储两个内容
fgets(string,string, 64, 64, stdin);
很明显,这不会起作用,但在C中是否有可能.我对C很新(2天).我知道在Java中你可以使用main和grab命令行条目中定义的args [],其中用户输入中的每个空格都是args数组中的不同元素.
我基本上需要知道我的 HashMap 是否有映射到相同值的不同键。我想知道除了检查每个键值与映射中的所有其他值之外是否还有其他方法。
更新： 只是一些更多的信息，希望能够澄清我想要完成的任务。考虑一个字符串“azza”。假设我正在迭代这个字符串并将每个字符存储为键，它的相应值是其他字符串。假设我最终到达最后一次出现的“a”，并且该值已经在映射中。如果与已在映射中的值对应的键也是“a”，那就没问题了。当“a”和“z”都映射到相同的值时，就会出现我的问题。仅当不同的键映射到相同的值时。