Question

1169. 查询无效交易

English Version

题目描述

如果出现下述两种情况，交易 可能无效：

• 交易金额超过 $1000
• 或者，它和 另一个城市 中 同名 的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）

给定字符串数组交易清单

 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。

返回 transactions，返回可能无效的交易列表。你可以按 任何顺序 返回答案。

 

示例 1：

输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
输出：["alice,20,800,mtv","alice,50,100,beijing"]
解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。

示例 2：

输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
输出：["alice,50,1200,mtv"]

示例 3：

输入：transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
输出：["bob,50,1200,mtv"]

 

提示：

• transactions.length <= 1000
• 每笔交易 transactions[i] 按 "{name},{time},{amount},{city}" 的格式进行记录
• 每个交易名称 {name} 和城市 {city} 都由小写英文字母组成，长度在 1 到 10 之间
• 每个交易时间 {time} 由一些数字组成，表示一个 0 到 1000 之间的整数
• 每笔交易金额 {amount} 由一些数字组成，表示一个 0 到 2000 之间的整数

解法

方法一：哈希表 + 模拟

遍历交易列表，对于每笔交易，如果金额大于 1000，或者同名且城市不同且时间间隔不超过 60 分钟，则将其加入答案。

具体地，我们使用哈希表 d 记录每个交易，其中键为交易名称，值为一个列表，列表中的每个元素为一个三元组 (time, city, index)，表示在 time 时刻在 city 城市进行了编号为 index 的交易。同时，我们使用哈希表 idx 记录答案中的交易编号。

遍历交易列表，对于每笔交易，我们首先将其加入哈希表 d 中，然后判断其金额是否大于 1000，如果是，则将其编号加入答案中。然后我们遍历哈希表 d 中的交易，如果交易名称相同且城市不同且时间间隔不超过 60 分钟，则将其编号加入答案中。

最后，我们遍历答案中的交易编号，将其对应的交易加入答案即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为交易列表的长度。

class Solution:
  def invalidTransactions(self, transactions: List[str]) -> List[str]:
    d = defaultdict(list)
    idx = set()
    for i, x in enumerate(transactions):
      name, time, amount, city = x.split(",")
      time, amount = int(time), int(amount)
      d[name].append((time, city, i))
      if amount > 1000:
        idx.add(i)
      for t, c, j in d[name]:
        if c != city and abs(time - t) <= 60:
          idx.add(i)
          idx.add(j)
    return [transactions[i] for i in idx]

class Solution {
  public List<String> invalidTransactions(String[] transactions) {
    Map<String, List<Item>> d = new HashMap<>();
    Set<Integer> idx = new HashSet<>();
    for (int i = 0; i < transactions.length; ++i) {
      var e = transactions[i].split(",");
      String name = e[0];
      int time = Integer.parseInt(e[1]);
      int amount = Integer.parseInt(e[2]);
      String city = e[3];
      d.computeIfAbsent(name, k -> new ArrayList<>()).add(new Item(time, city, i));
      if (amount > 1000) {
        idx.add(i);
      }
      for (Item item : d.get(name)) {
        if (!city.equals(item.city) && Math.abs(time - item.t) <= 60) {
          idx.add(i);
          idx.add(item.i);
        }
      }
    }
    List<String> ans = new ArrayList<>();
    for (int i : idx) {
      ans.add(transactions[i]);
    }
    return ans;
  }
}

class Item {
  int t;
  String city;
  int i;

  Item(int t, String city, int i) {
    this.t = t;
    this.city = city;
    this.i = i;
  }
}

class Solution {
public:
  vector<string> invalidTransactions(vector<string>& transactions) {
    unordered_map<string, vector<tuple<int, string, int>>> d;
    unordered_set<int> idx;
    for (int i = 0; i < transactions.size(); ++i) {
      vector<string> e = split(transactions[i], ',');
      string name = e[0];
      int time = stoi(e[1]);
      int amount = stoi(e[2]);
      string city = e[3];
      d[name].push_back({time, city, i});
      if (amount > 1000) {
        idx.insert(i);
      }
      for (auto& [t, c, j] : d[name]) {
        if (c != city && abs(time - t) <= 60) {
          idx.insert(i);
          idx.insert(j);
        }
      }
    }
    vector<string> ans;
    for (int i : idx) {
      ans.emplace_back(transactions[i]);
    }
    return ans;
  }

  vector<string> split(string& s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }
};

func invalidTransactions(transactions []string) (ans []string) {
  d := map[string][]tuple{}
  idx := map[int]bool{}
  for i, x := range transactions {
    e := strings.Split(x, ",")
    name := e[0]
    time, _ := strconv.Atoi(e[1])
    amount, _ := strconv.Atoi(e[2])
    city := e[3]
    d[name] = append(d[name], tuple{time, city, i})
    if amount > 1000 {
      idx[i] = true
    }
    for _, item := range d[name] {
      if city != item.city && abs(time-item.t) <= 60 {
        idx[i], idx[item.i] = true, true
      }
    }
  }
  for i := range idx {
    ans = append(ans, transactions[i])
  }
  return
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

type tuple struct {
  t  int
  city string
  i  int
}