leetcode
leetcode 1101 ~ 1150
查询无效交易

查询无效交易

难度:

标签:

题目描述

代码结果

运行时间: 47 ms, 内存: 16.5 MB


import java.util.*;
import java.util.stream.*;

public class Solution {
    /**
     * 思路:
     * 使用Java Stream API来过滤无效交易:
     * 1. 解析交易信息。
     * 2. 检查每个交易,判断其金额是否超过1000。
     * 3. 对于每个交易,检查是否有其他交易在60分钟内发生并且城市不同。
     * 4. 将无效交易存入结果列表并返回。
     */
    public List<String> invalidTransactions(String[] transactions) {
        List<Transaction> transactionList = Arrays.stream(transactions)
            .map(Transaction::new)
            .collect(Collectors.toList());

        return transactionList.stream()
            .filter(t1 -> t1.amount > 1000 || transactionList.stream().anyMatch(t2 -> t1.isInvalid(t2)))
            .map(Transaction::toString)
            .collect(Collectors.toList());
    }

    class Transaction {
        String name;
        int time;
        int amount;
        String city;
        String raw;

        Transaction(String transaction) {
            String[] parts = transaction.split(",");
            this.name = parts[0];
            this.time = Integer.parseInt(parts[1]);
            this.amount = Integer.parseInt(parts[2]);
            this.city = parts[3];
            this.raw = transaction;
        }

        boolean isInvalid(Transaction t2) {
            return this != t2 && this.name.equals(t2.name) && !this.city.equals(t2.city) && Math.abs(this.time - t2.time) <= 60;
        }

        @Override
        public String toString() {
            return this.raw;
        }
    }
}

解释

方法:

这个题解使用了哈希表来跟踪每个人的交易记录,并检查每个交易是否有效。首先,通过遍历每个交易字符串,它解析出交易者的姓名、时间、金额和城市,并将时间和城市存储在哈希表中,键为交易者姓名。之后,再次遍历每个交易,首先检查交易金额是否超过1000美元,如果是,则将其添加到无效交易列表中。接着,对于没有直接因金额超标而无效的交易,它会检查同一个人的其他交易记录,看是否有在不同城市且时间差在60分钟以内的交易,如果有,该交易也被认为是无效的。这个方法保证了能检测出题目中定义的所有无效交易情况。

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
算法中似乎对每一笔交易都进行了遍历检查其他交易记录,这是否意味着算法效率较低?有没有可能通过优化数据结构或算法逻辑来提高效率?
是的,当前算法的效率可能较低,因为它对每个交易进行了遍历,并且对每个交易再次遍历该交易者的所有交易记录来检查条件,这使得时间复杂度接近O(n^2),其中n是交易的数量。可以通过以下方式优化算法:1. 使用更复杂的数据结构,例如哈希表中不仅存储时间和城市,还可以存储交易索引和金额,这样可以更快速地进行查找和比较。2. 对每个交易者的交易记录按时间排序,然后使用两个指针的方法来检查60分钟内的其他交易,这样可以减少不必要的比较,从而提高效率。
🦆
在最后返回结果时,是否存在重复交易被多次添加到结果列表中的可能性?如果有,如何优化算法以避免重复添加?
是的,存在重复交易被多次添加到结果列表中的可能性。例如,如果一笔交易因为金额超过1000美元而被添加到结果中,而后又因为与另一笔交易在不同城市且时间差在60分钟内被再次添加,这就导致了重复。为了避免这种情况,可以在添加到结果列表之前检查该交易是否已经存在于结果中。更有效的方法是使用集合(Set)来存储结果,因为集合自动处理重复项,这样即使尝试添加重复的交易,也不会在结果集合中重复出现。

相关问题