油耗追踪程序日期与里程表输入验证算法实现优化求助

现有问题梳理 #

• 逻辑缺陷：未完整覆盖同日期输入的校验规则、插入列表末尾的校验逻辑缺失、验证不通过时仍然输出添加成功提示
• 效率问题：当前用线性遍历查找插入位置和查重，数据量较大时时间复杂度为O(n)，性能较差

优化实现思路 #

1. 效率优化 #

由于数据集本身是按时间倒序排序的，可使用二分查找定位插入位置，将查找复杂度从O(n)降低到O(logn)；如果数据集规模较大，可额外用HashSet存储<日期,里程>的组合，把查重复杂度降到O(1)，小数据集保留线性遍历也可满足需求。

2. 校验逻辑完善 #

严格对齐规则实现分层校验：

1. 第一步先查重，日期+里程组合重复直接拦截
2. 找到插入位置后分三种场景校验：
   • 插入顶部（索引为0）：如果输入日期晚于最新条目，里程必须大于最新条目里程；如果和最新条目日期相同，里程要小于最新条目里程，同时早于更早日期的对应里程
   • 插入中间：输入里程必须小于插入位置前一条的里程，大于插入位置当前条的里程
   • 插入末尾：输入里程必须小于最早条目的里程

优化后核心代码示例 #

import java.util.Objects;

// 可选：封装加油条目，统一管理日期和里程，降低维护成本
record FuelRecord(Date date, int odometer) {}

public class OdometerValidator {
    public static Date[] dates = new Date[3];
    public static int[] odometers = new int[3];

    // 初始化示例数据集
    static {
        dates[0] = new Date(2021,2,14);
        dates[1] = new Date(2021,2,5);
        dates[2] = new Date(2021,2,4);
        odometers[0] = 156830;
        odometers[1] = 156572;
        odometers[2] = 156255;
    }

    public static void main(String[] args) {
        // 测试输入
        Date inputDate = new Date(2021,2,14);
        int inputOdo = 156255;

        // 第一步：重复校验
        if (hasDuplicate(inputDate, inputOdo)) {
            System.out.println("该日期和里程组合的加油记录已存在。");
            return;
        }

        // 第二步：二分查找插入位置，复杂度O(logn)
        int insertIndex = findInsertIndex(inputDate);
        boolean isValid = true;

        // 第三步：按插入位置做里程校验
        if (insertIndex == 0) {
            // 插入顶部场景
            if (inputDate.compareTo(dates[0]) > 0) {
                // 日期晚于最新条目，里程必须大于最新里程
                if (inputOdo <= odometers[0]) {
                    System.out.printf("里程不能小于您此前记录的加油里程：%d（日期：%s）%n", odometers[0], dates[0]);
                    isValid = false;
                }
            } else {
                // 和最新条目日期相同，里程需符合相邻递增规则
                if (inputOdo >= odometers[0] || (dates.length > 1 && inputOdo <= odometers[1])) {
                    System.out.printf("里程需介于%d（日期：%s）和%d（日期：%s）之间%n",
                            odometers[1], dates[1], odometers[0], dates[0]);
                    isValid = false;
                }
            }
        } else if (insertIndex == dates.length) {
            // 插入末尾场景
            if (inputOdo >= odometers[dates.length - 1]) {
                System.out.printf("里程不能大于您此前记录的最早加油里程：%d（日期：%s）%n", odometers[dates.length-1], dates[dates.length-1]);
                isValid = false;
            }
        } else {
            // 插入中间场景
            int upperOdo = odometers[insertIndex - 1];
            int lowerOdo = odometers[insertIndex];
            if (inputOdo >= upperOdo || inputOdo <= lowerOdo) {
                System.out.printf("里程需介于%d（日期：%s）和%d（日期：%s）之间%n", lowerOdo, dates[insertIndex], upperOdo, dates[insertIndex-1]);
                isValid = false;
            }
        }

        if (isValid) {
            System.out.println("加油记录添加成功！");
            // 此处可实现数组扩容、插入新条目的逻辑
        }
    }

    // 二分查找定位插入位置
    private static int findInsertIndex(Date inputDate) {
        int left = 0, right = dates.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (inputDate.compareTo(dates[mid]) >= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 查重方法，大数据集可替换为HashSet实现O(1)查重
    private static boolean hasDuplicate(Date date, int odo) {
        for (int i = 0; i < dates.length; i++) {
            if (date.equals(dates[i]) && odo == odometers[i]) {
                return true;
            }
        }
        return false;
    }

    // 简化日期实现，仅做示例，生产环境可使用java.time包下的LocalDate
    static class Date implements Comparable<Date> {
        int year, month, day;
        public Date(int year, int month, int day) {
            this.year = year;
            this.month = month;
            this.day = day;
        }
        @Override
        public int compareTo(Date o) {
            if (year != o.year) return year - o.year;
            if (month != o.month) return month - o.month;
            return day - o.day;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Date date = (Date) o;
            return year == date.year && month == date.month && day == date.day;
        }
        @Override
        public int hashCode() {
            return Objects.hash(year, month, day);
        }
        @Override
        public String toString() {
            return year + "-" + month + "-" + day;
        }
    }
}

内容的提问来源于stack exchange，提问作者aldrich19