8.25 more arrays (c++ set)

- Find Minimum in Rotated Sorted Array

• it counts when it's not roated
• note the while loop condition to avoid basecase embedded within loop body

    int findMin(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        if (n==1) return nums[0];
        int left = 0, right = n-1;
        //not rotated at all
        if (nums[left]<nums[right]) return nums[left]; 
        
        while (left < right-1) { // trick: stop when left == right-1
            int mid = left + (right-left)/2;
            if (nums[left]<=nums[mid]) left = mid;
            else right = mid;
        }
        return min(nums[left], nums[right]);
    }

- Find Minimum in Rotated Sorted Array II

• note the array may become "unrotated" during processing in this case

    int findMin(vector<int>& nums) {
        int n = nums.size();
        if (!n) return INT_MIN;
        if (n==1) return nums[0];
        int left = 0, right = n-1;
        
        while (left < right-1) {
            if (nums[left]<nums[right]) return nums[left];
            int mid = left + (right-left)/2;
            if (nums[left]<nums[mid]) left = mid;
            else if (nums[left]==nums[mid]) ++left;
            else right = mid;
        }
        return min(nums[left], nums[right]);
    }

- Shuffle an Array

• random_shuffle()用来对一个元素序列重新排序
• no need to specify the last gen random seed func, just for fun

class Solution {
public:
    Solution(vector<int> nums) {
        original = curr = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        curr = original;
        return curr;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        random_shuffle(curr.begin(), curr.end(), [](int i){ return rand()%i; });
        return curr;
    }
private: 
    vector<int> original;
    vector<int> curr;
};

- intersection-of-two-arrays

Set vs. unordered_set

• store unique elements following a specific order
• where the value of an element also identifies it (the value is itself the key, of type T). Elements cannot be modified, but can be deleted/added
• internally, the elements in a set are always sorted following a specific strict weak ordering
• set containers are generally slower than unordered_set containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.Sets are typically implemented as binary search trees.

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        vector<int> ret;
        for (int i : nums2) 
            if (set1.erase(i)) // return # of erased els
                ret.push_back(i);
            
        return ret;
    }

- Intersection of Two Arrays II

1. hash table (Time: O(m+n); Space: O(m+n))

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        for (int i :nums1) ++map[i];
        vector<int> ret;
        for (int i :nums2) {
            if (map.find(i)!=map.end()) {
                if (--map[i]==0) map.erase(i);
                ret.push_back(i);
            }
        }
        return ret;
    }

2.

map fun fact..
if a key is not exist, access the key will assign a default value to the key. Means if you simply test if map[key] is 0 or not by using if (map[key]) without testing if the key is in the map, you will consume extra space

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        for (int i :nums1) ++map[i];
        vector<int> ret;
        for (int i :nums2) {
            if (map.find(i)!=map.end()) {
                if (--map[i]==0) map.erase(i);
                ret.push_back(i);
            }
        }
        return ret;
    }

mark: do w/ 2 ptrs

- Product of Array Except Self

• consider edge case..

mark: quick try

    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, 1);
        for (int i=1; i<n; ++i) {
            ret[i] = ret[i-1]*nums[i-1];
        }
        int acc = 1;
        for (int i=n-2; i>=0; --i) {
            acc *= nums[i+1];
            ret[i] *= acc;
        }
        return ret;
    }