Sort

164. Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        size_t len = nums.size();
        if (len < 2) return 0;
        radixSort(nums);
        int max_gap = 0;
        for (int i = 1; i < nums.size(); ++i) {
            max_gap = max(max_gap, nums[i] - nums[i-1]);
        }

        return max_gap;
    }

    void radixSort(vector<int>& nums) {
        int max_num = INT_MIN;
        for (auto num : nums) max_num = max(max_num, num);

        for (int exp = 1; max_num / exp > 0; exp *= 10) {
            countSort(nums, exp);
        }
    }

    void countSort(vector<int>& nums, int exp) {
        vector<int> sorted(nums.size());
        vector<int> count(10, 0);

        for (auto num : nums) {
            size_t index = (num / exp) % 10;
            count[index]++;
        }

        for (size_t i = 1; i < count.size(); ++i) {
            count[i] += count[i-1];
        }

        for (size_t i = nums.size(); i != 0; --i) {
            size_t index = (nums[i-1] / exp) % 10;
            sorted[count[index]-1] = nums[i-1];
            count[index]--;
        }

        nums = sorted;
        //swap(nums, sorted);
    }
};

41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        size_t len = nums.size();
        if (!len) return 1;

        for (size_t i = 0; i < len; ++i) {
            while (nums[i] != i + 1 && nums[i] > 0 && nums[i] < len) {
                int t = nums[i];
                if (nums[t - 1] == t) break;
                nums[i] = nums[t - 1];
                nums[t - 1] = t;
            }
        }

        for (size_t i = 0; i < len; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return len + 1;
    }
};

179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer.

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        auto cmp = [](int a, int b) {
            return to_string(a) + to_string(b) > to_string(b) + to_string(a);
        };
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for (auto n : nums) {
            // if (n == 0 && res == "") continue;
            res += to_string(n);
        }
        size_t i = 0;
        for(; i < res.size(); ++i) {
            if (res[i] != '0') break;
        }
        res = res.substr(i);

        if (res == "") res = "0";
        return res;
    }
};

215. Kth Largest Element in an Array

ind the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given [3,2,1,5,6,4] and k = 2, return 5.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        if (k > len) return -1;
        nth_element(nums.begin(), nums.begin() + len - k, nums.end());
        return *(nums.begin() + len - k);
    }

    int kth_element(vector<int>& nums, int k, int start, int end) {
        if (start > end) return -1;
        int pivot = nums[end];
        int i = start, j = start;
        while (i < end) {
            if (nums[i] > pivot) swap(nums[i++], nums[j++]);
            else i++;
        }
        swap(nums[j], nums[end]);
        int cur_len = j - start + 1;
        if (cur_len == k) return nums[j];
        else if (cur_len > k) return kth_element(nums, k, start, j - 1);
        else return kth_element(nums, k - cur_len, j + 1, end);

    }
};

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        // multiset<long long> window;
        // int len = nums.size();
        // if (!len || k <= 0) return false;
        // int start = 0;
        // for (size_t i = 0; i < len; ++i) {
        //     if (window.size() >= k + 1) {
        //         auto it = window.find(nums[start++]);
        //         window.erase(it);
        //     }
        //     if (window.size()) {
        //         auto it = window.lower_bound(nums[i]);
        //         if (it != window.end() && labs(*it - nums[i]) <= t) return true;
        //         else if (it != window.begin() && labs(*--it - nums[i]) <= t) return true;

        //     }
        //     window.insert(nums[i]);
        // }

        // return false;
        int len = nums.size();
        if (!len || k <= 0 || t < 0) return false;

        unordered_map<long long, long long> buckets;
        t = abs(t);
        for (size_t i = 0; i < len; ++i) {
            long long maped = static_cast<long long>(nums[i]) - INT_MIN;
            long long bucket_id = maped / (t + 1);
            if (buckets.find(bucket_id) != buckets.end()) return true;
            if (buckets.find(bucket_id-1) != buckets.end() && labs(maped - buckets[bucket_id-1]) <= t) return true;
            if (buckets.find(bucket_id+1) != buckets.end() && labs(buckets[bucket_id+1] - maped) <= t) return true;
            if (buckets.size() >= k) {
                long long last_bucket_id = (static_cast<long long>(nums[i-k]) - INT_MIN) / (t + 1);
                buckets.erase(last_bucket_id);
            }
            buckets[bucket_id] = maped;
        }
        return false;
    }
};

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        size_t len = nums.size();
        for (size_t i = 0; i < len; ++i) {
            while (nums[i] != i && nums[i] >= 0 && nums[i] < len) {
                int t = nums[i];
                if (t == nums[t]) break;
                nums[i] = nums[t];
                nums[t] = t;
            }
        }
        for (size_t i = 0; i < len; ++i) {
            if (nums[i] != i) return i;
        }
        return len;
    }
};

280 Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        for (size_t i = 1; i < nums.size(); ++i) {
            if (i%2 == nums[i-1] > nums[i]) swap(nums[i-1], nums[i]);
        }
    }
};

296 Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Hint:

Try to solve it in one dimension first. How can this solution apply to the two dimension case?

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        size_t m = grid.size();
        size_t n = grid[0].size();
        vector<int> x, y;

        for (size_t i = 0; i < m; i++) {
            for (size_t j = 0; j < n; j++) {
                if (grid[i][j]) {
                    x.push_back(j);
                    y.push_back(i);
                }
            }
        }

        nth_element(x.begin(), x.begin() + x.size()/2, x.end());
        int midx = x[x.size()/2];
        int midy = y[y.size()/2];

        int dist = 0;
        for (size_t i = 0; i < m; i++) {
            for (size_t j = 0; j < n; j++) {
                if (grid[i][j]) {
                    dist += abs(int(i) - midy);
                    dist += abs(int(j) - midx);
                }
            }
        }
        return dist;
    }
};

315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. Return the array [2, 1, 1, 0].

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        vector<pair<int, int>> data;
        for (size_t i = 0; i < nums.size(); ++i) {
            data.push_back({nums[i], i});
        }
        countWhileMerge(data, res);
        return res;
    }
    void countWhileMerge(vector<pair<int, int>>& data, vector<int>& res) {
        size_t len = data.size();
        if (len <= 1) return;

        size_t mid = len / 2;
        vector<pair<int, int>> left(data.begin(), data.begin() + mid);
        vector<pair<int, int>> right(data.begin() + mid, data.end());

        countWhileMerge(left, res);
        countWhileMerge(right, res);
        int i = left.size();
        int j = right.size();
        for (int k = data.size() - 1; k >= 0; --k) {
            if (j == 0 || (i > 0 && left[i - 1].first > right[j-1].first)) {
                res[left[i-1].second] += j;
                data[k] = left[--i];
            } else {
                data[k] = right[--j];
            }
        }
    }
};

324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        size_t len = nums.size();
        nth_element(nums.begin(), nums.begin() + len/2, nums.end());

        int median = *(nums.begin() + len/2);
        int i = 0;
        int n = len - 1;
        int j = 0;
        while (i <= n) {
            if (nums[i] > median) {
                swap(nums[i], nums[n--]);
            } else if (nums[i] < median) {
                swap(nums[i++], nums[j++]);
            } else {
                ++i;
            }
        }
        auto copied = nums;
        // for (auto n : copied) cout << n << " ";
        int mid = (len-1)/2;
        for (size_t i = 0; i < nums.size() && mid >= 0; i += 2) {
            nums[i] = copied[mid--];
        }
        int last = len - 1;
        for (size_t i = 1; i < nums.size() && last >= 0; i += 2) {
            nums[i] = copied[last--];
        }
    }
};

327. Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long> sums(nums.size() + 1);
        for (size_t i = 0; i < nums.size(); ++i) {
            sums[i+1] = sums[i] + nums[i];
        }
        return countWhileMergeSort(sums, lower, upper, 0, sums.size());
    }

    int countWhileMergeSort(vector<long>& sums, int lower, int upper, int start, int end) {
        if (end - start <= 1) return 0;
        int mid = start + (end - start)/2;
        int count = countWhileMergeSort(sums, lower, upper, start, mid) + 
                    countWhileMergeSort(sums, lower, upper, mid, end);

        vector<long> cache;
        int j = mid, k = mid, t = mid;
        for (size_t i = start, r = 0; i < mid; ++i, ++r) {
            while(k < end && (sums[k] - sums[i] < lower)) ++k;
            while(j < end && (sums[j] - sums[i] <= upper)) ++j;
            count += j - k;

            while (t < end && sums[t] < sums[i]) cache.push_back(sums[t++]);
            cache.push_back(sums[i]);
        }

        copy(cache.begin(), cache.end(), sums.begin() + start);

        return count;
    }
};

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

1 selection algorithm:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        if (!nums.size()) return res;
        unordered_map<int, int> cnt;
        for (auto num : nums) cnt[num]++;
        vector<pair<int, int>> num_with_cnt;
        for (auto kv : cnt) {
            num_with_cnt.push_back({kv.first, kv.second});
        }
        nth_element(num_with_cnt.begin(), num_with_cnt.begin() + k, num_with_cnt.end(), [](pair<int, int> &a, pair<int, int>& b) {
            return a.second > b.second;
        });
        for (int i = 0; i < k && i < num_with_cnt.size(); ++i) {
            res.push_back(num_with_cnt[i].first);
        }
        return res;
    }
};

2. PQ

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        unordered_map<int, int> cnt;
        for (auto num : nums) cnt[num]++;
        for (auto kv : cnt) {
            pq.push({kv.second, kv.first});
            while (pq.size() > k) pq.pop();
        }

        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

bucket sort

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> res;
        if (!nums.size()) return res;
        unordered_map<int, int> cnt;
        for (auto num : nums) cnt[num]++;
        vector<vector<int>> bucket(nums.size() + 1);
        for (auto kv : cnt) {
            bucket[kv.second].push_back(kv.first);
        }

        for (int i = bucket.size() - 1; i >= 0; --i) {
            for (int j = 0; j < bucket[i].size(); ++j){
                res.push_back(bucket[i][j]);
                if (res.size() == k) return res;
            }
        }

        return res;
    }
};

螺钉和螺母问题

假设我们有n个直径各不相同的螺钉，以及n个相应的螺母。我们一次只能比较一对螺钉和螺母，来判断螺母是大于螺钉、小于螺钉还是正好适合螺钉。然而，我们不能拿两个螺母做比较，也不能拿两个螺钉做比较。我们的问题是要找到每一对匹配的螺钉和螺母。为该问题设计一个算法，它的平均效率必须属于集合O(nlogn)。 思路：随便选一个螺钉，然后在螺母中找到匹配的那个，并把螺母分成大于与小于该螺钉的两组。然后根据匹配的螺母，把螺钉分成两组。遍历，直到全部排好序。

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
void print(int* array, int n)
{
    for (int i = 0; i < 7; ++i)
    {
        std::cout << left;
        std::cout << setw(3) << array[i] << " ";
    }
    std::cout << std::endl;
}
//---------------------------------------------------
int get_random_nut(int* nuts, int left, int right, int n)
{
    if (!nuts || right < left) return -1;
    return nuts[left+n];
}
//---------------------------------------------------
int get_match_bolt(int* bolts, int nut_pivot, int left, int right, int& index)
{
    if (!bolts || right < left) return -1;
    for (int i = left; i <= right; ++i)
    {
        if (bolts[i] == nut_pivot)
        {
            index = i;
            return bolts[i];
        }
    }
    return -1;
}
//---------------------------------------------------
int partition(int pivot, int index, int* array, int left, int right)
{
    if (!array || right <= left) return -1;
    int indexl(left), indexr(right);
    while (indexl <= indexr)
    {
        while (array[indexl] <= pivot && indexl <= indexr) {++indexl;}
        while (array[indexr] >= pivot && indexl <= indexr) {--indexr;}
        if (indexl <= indexr)
        {
            std::swap(array[indexl], array[indexr]);
            ++indexl;
            --indexr;
        }
    }
    indexr = max(indexr, left);
    std::swap(array[indexr], array[index]);
    return indexr;
}
//---------------------------------------------------
void match_nut_bolt(int* nuts, int*bolts, int left, int right)
{
    // set bolt pivot and it's position, get nut pivot and it's position
    int bolt_pos(0);
    int nut_pivot = get_random_nut(nuts, left, right, 0);
    int bolt_pivot = get_match_bolt(bolts, nut_pivot*10, left, right, bolt_pos);
    // partition
    int index_nut = partition(bolt_pivot/10, 0+left, nuts, left, right);
    print(nuts, 7);
    int index_bolt = partition(nut_pivot*10, bolt_pos, bolts, left, right);
    print(bolts, 7);
    if (index_bolt != index_nut)
    {
        std::cout << "error" << std::endl;
    }
    // recursive
    if (left < index_nut-1)
    {
        match_nut_bolt(nuts, bolts, left, index_nut-1);
    }
    if (right > index_nut+1)
    {
        match_nut_bolt(nuts, bolts, index_nut+1, right);
    }
}
//---------------------------------------------------
void match_nut_bolt(int* nuts, int* bolts, int n)
{
    if (!nuts || !bolts || n < 2) return;
    match_nut_bolt(nuts, bolts, 0, n-1);
}
int main()
{
    int nuts[7] = {5,4,6,2,7,1,3};
    int bolt[7] = {40,10,20,50,30,70,60};
    //int nuts[7] = {4,1,2,5,3,7,6};
    //int bolt[7] = {50,40,60,20,70,10,30};
    match_nut_bolt(nuts, bolt, 7);
    std::cout << "nuts:    ";
    print(nuts, 7);
    std::cout << "bolts:    ";
    print(bolt, 7);
    std::cout << std::endl;
    system("Pause");
}

void sort_two_groups(vector<int>& a, vector<int>& b) {
    auto partition = [&](vector<int>& arr, int l, int r, int pivot) {
        int e = l;
        while(e <= r) {
            if(arr[e] < pivot) swap(arr[l++], arr[e++]);
            else if(arr[e] > pivot) swap(arr[e], arr[r--]);
            else e++;
        }
        return l;
    };
    function<void(int,int)> sort = [&](int l, int r) {
        if(l >= r) return;
        int val_a = a[l + (rand() % (r - l + 1))];

        int pivot = partition(b, l, r, val_a);
        partition(a, l, r, b[pivot]);

        sort(l, pivot - 1);
        sort(pivot + 1, r);
    };
    sort(0, (int)a.size() - 1);
}

Alphabetical Sorting

{ “face”, “ball”, “apple”, “art”, “ah” }
“htarfbp…”
根据下面的string去给上面list words排序。就是平常我们按abcd…排，这次按string里的letter顺序排

void str_sort(vector<string>& strs, const string& dict) {
    unordered_map<char, int> ranks;
    for(int i = 0; i < dict.size(); ++i) {
        ranks[dict[i]] = i;
    }
    sort(strs.begin(), strs.end(), [&ranks](const string& a, const string& b) {
        size_t len = std::min(a.length(), b.length());
        for(size_t i = 0; i < len; ++i) {
            auto r = ranks[a[i]] - ranks[b[i]];
            if(r < 0) return true;
            else if(r > 0) return false;
        }
        return a.length() < b.length();
    });
}