英文:
count two arraylist A and B and count values in A which are less than each num of B
问题
给定两个ArrayList A 和 B，A={3,4,5]，B=[4,7]，统计在A中有多少个数字小于或等于B中的每个元素。在这个案例中，B.get(0)=4 有2个值小于或等于A，即3和4，同样7有3个值。因此，函数应该返回list=[2,3]。
我已经使用两个for循环解决了这个问题，对于较小的输入可以工作，但随着大小的增长，性能会下降。
import java.util.*;
public class checkDiff {
public static void check(List<Integer> A, List<Integer> B) {
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < B.size(); i++) {
int count = 0;
for (int j = 0; j < A.size(); j++) {
if (A.get(j) <= B.get(i)) {
count++;
}
}
result.add(i, count);
}
for (int x : result) {
System.out.println(x);
}
}
public static void main(String[] args) {
List<Integer> A = new ArrayList<Integer>();
List<Integer> B = new ArrayList<Integer>();
A.add(3);
A.add(4);
A.add(7);
B.add(4);
B.add(7);
check(A, B);
}
}
有没有办法优化这段代码？请帮助。
英文:
Given two arraylist A and B, A={3,4,5] and B=[4,7], count how many numbers in A are less or equal than each element in B. In this case B.get(0)=4 is has 2 values less or equal in A,i.e 3 and 4, similarly 7 has 3 values. So the function should return list=[2,3].
I have solved this question using two for loops, which works for smaller inputs ,however as the size grows the performance is degraded.
import java.util.*;
public class checkDiff{
public static void check(List<Integer> A, List<Integer> B) {
List<Integer> result=new ArrayList<Integer>();
for(int i=0;i<B.size();i++){
int count=0;
for(int j=0;j<A.size();j++){
if(A.get(j)<=B.get(i)){
count++;
}
}
result.add(i,count);
}
for(int x:result){
System.out.println(x);
}
}
public static void main(String []args){
List<Integer> A=new ArrayList<Integer>();
List<Integer> B=new ArrayList<Integer>();
A.add(3);
A.add(4);
A.add(7);
B.add(4);
B.add(7);
check(A,B);
}
}
Is there any way to optimize this code.Please help.
答案1
得分: 0
问题在于您正在处理一个未按值排序的数组。因此，您将不得不检查所有可能的组合，除非您使用已排序的列表或使用类似二叉搜索树的数据结构，否则您无法加速此过程。
英文:
The thing is that you are taking an array which is not sorted value wise. Hence you will have to check all the possible combinations and you cannot make this process faster unless and until you use a sorted list or use data structure like binary search tree.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论