问题遇到的现象和发生背景
leetocde上第825题循环过程加上break执行效率反而慢了4秒,按照逻辑来说break能减少循环及运算次数,程序执行效率应该加快才对。题目地址:https://leetcode-cn.com/problems/friends-of-appropriate-ages/submissions/
问题相关代码,请勿粘贴截图
class Solution {
// 快速排序
public void quickSort(int[] nums, int left, int right) {
if (left >= right)
return;
int temp = nums[left];
int l = left;
int r = right;
while (l < r) {
while (nums[r] <= temp && l < r) {
r--;
}
while (nums[l] >= temp && l < r) {
l++;
}
if (l < r) {
int t = nums[r];
nums[r] = nums[l];
nums[l] = t;
}
}
nums[left] = nums[r];
nums[r] = temp;
quickSort(nums, left, l - 1);
quickSort(nums, l + 1, right);
}
public int numFriendRequests(int[] ages) {
int sum = 0;
Map<Integer, Integer> map = new HashMap<>();
// 用HashMap记录各个年龄及其对应人数
for (int age : ages) {
map.put(age, map.getOrDefault(age, 0) + 1);
}
int[] ages1 = new int[map.size()];
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
int a = 0;
// 用数组ags1储存各个年龄的同时,处理年龄相等情况下的好友请求情况
while (it.hasNext()) {
Map.Entry<Integer, Integer> entry = it.next();
ages1[a++] = entry.getKey().intValue();
if (entry.getValue().intValue() != 1) {
// 年龄相等则可排除除条件age[y] > age[x]和age[y] > 100 && age[x] < 100
if (!(entry.getKey() <= 0.5 * entry.getKey() + 7)) {
sum += (entry.getValue() - 1) * entry.getValue();
}
}
}
// 排序保证数组降序
quickSort(ages1, 0, ages1.length - 1);
// 循环时由于数组降序保证x<y即可排除条件age[y] > age[x]和age[y] > 100 && age[x] < 100
for (int x = 0; x < ages1.length - 1; x++) {
for (int y = x + 1; y < ages1.length; y++) {
// 处理ages1[x]<ages1[y]的情况下的好友请求情况
if (!(ages1[y] <= (0.5 * ages1[x] + 7))){
sum += map.get(ages1[x]).intValue() * map.get(ages1[y]).intValue();
}else break;// 这里如果不要break程序执行结果会快四秒
}
}
return sum;
}
}
运行结果及报错内容
这是加上break后的运行结果:
这是去掉break后的运行结果:
我的解答思路和尝试过的方法
我的大致思路为用哈希map储存各个年龄和该年龄对应的人数,用数组ages1储存各个年龄,再对ages1降序排序,循环时保证x<y即可不用再考虑限制条件二和三(age[y] > age[x]和age[y] > 100 && age[x] < 100),若年龄ages1[x]的人给ages1[x]的人发送好友请求,总数应为ages1[x]年龄对应的人数乘以(ages1[x]年龄对应的人数-1),若ages1[x]的人给ages1[y]的人发送好友请求,总数应为两个年龄端对应人数相乘。
加上break的思想在于对于条件一:age[y] <= 0.5 * age[x] + 7,若找到第一个该条件后面为真,对于同一个x后面所有的y这个条件也为真,因为数组降序排列
我想要达到的结果
按照逻辑来说break能减少循环及运算次数,程序执行效率应该加快才对。但是加上break后反而变慢了,始终不知道为什么加上break会反而变慢