2295. Replace Elements in an Array

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        unordered_map<int,int> mp;
        int n = nums.size();
        for(int i=0;i<n;++i) mp[nums[i]] = i;
        for( auto op : operations){
            nums[mp[op[0]]] = op[1];
            mp[op[1]] = mp[op[0]];
            mp.erase(op[0]); // option
        }
        return nums;
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(n) can reduce O(1)