查询无效交易
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
算法中似乎对每一笔交易都进行了遍历检查其他交易记录,这是否意味着算法效率较低?有没有可能通过优化数据结构或算法逻辑来提高效率?
▷🦆
在最后返回结果时,是否存在重复交易被多次添加到结果列表中的可能性?如果有,如何优化算法以避免重复添加?
▷