排序

题十一：重排并计算逆序数

腾讯2019校招

作为程序员的小Q，它的数列和其他人的不太一样，他有 $2^{n}$ 个数。老板问了小Q一共m次，每次给出一个整数 $q_{i}$ (1⇐i⇐m)，要求小Q把这些数每 $2^{q_{i}}$ 分为一组，然后把每组进行翻转，小Q想知道每次操作后整个序列中的逆序对个数是多少呢？

例如：对于序列1 3 4 2，逆序对有(4,2), (3,2)总数量为2. 翻转之后为2 4 3 1，逆序对有(2,1), (4,3), (4,1), (3,1)总数量为4.

输入描述：第一行一个数n（0⇐n⇐20）第二行 $2^{n}$ 个数，表示初始序列（1⇐初始序列⇐ $1 0^{9}$ ）第三行一个数m（1⇐m⇐ $1 0^{6}$ ）第四行m个数表示 $q_{i}$ (0⇐ $q_{i}$ ⇐n)

输出描述： m行每行一个数表示答案

输入示例：

输出示例：

说明：初始序列2 1 4 3 $2^{q_{1}} = 2$ → 第一次：1 2 3 4 → 逆序对数0 $2^{q_{2}} = 4$ → 第二次：4 3 2 1 → 逆序对数6 $2^{q_{3}} = 1$ → 第三次：4 3 2 1 → 逆序对数6 $2^{q_{4}} = 4$ → 第四次：1 2 3 4 → 逆序对数0

首先如何计算逆序数，常用的方法是归并排序，可以顺带计算逆序数。但是由于我一开始用的是开销较大的归并，频繁的构造，复制vector，导致运行超时。后来改成了inplace的归并，速度明显提高很多。

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
 
using namespace std;
 
// combine two sorted subseqs
vector<int> merge(vector<int>& a, vector<int>& b, int* invcount)
{
  vector<int> res; // result seq
  vector<int>::iterator i = a.begin();
  vector<int>::iterator j = b.begin();
  while(i != a.end() && j != b.end())
  {
    if (*i <= *j) res.push_back(*(i++));
    if (*i > *j)
    {
    	res.push_back(*(j++));
    	(*invcount) += (a.end() - i);
    }
  }
	
  // tail appending ...
  if (i == a.end())
  {
    for(auto iter = j; iter != b.end(); ++iter)
      res.push_back(*iter);
  }
  if (j == b.end())
  {
    for(auto iter = i; iter != a.end(); ++iter)
      res.push_back(*iter);
  }
  
  return res;
}
 
// 归并排序的递归形式
vector<int> mergesort(vector<int>& seq, int* invcount)
{
  if (seq.size() == 1) return seq;
  else{
    // split the seq into two subseqs
    int lsize = seq.size() >> 1;
    vector<int> tmpl(seq.begin(), seq.begin() + lsize);
    vector<int> tmpr(seq.begin() + lsize, seq.end());
    
    vector<int> lseq, rseq;
    // recursively slove subproblems 
    lseq = mergesort(tmpl, invcount);
    rseq = mergesort(tmpr, invcount);
    
    return merge(lseq, rseq, invcount);
  }
}
 
// in-place merge sort
namespace inplace
{
/// Merge two sorted range [beg, mid), [mid, end).
void Merge(vector<int>& arr, int beg, int mid, int end, int* invcnt)
{
  for (int i = beg, j = mid; i < mid && j < end;)
  {
    if (arr[i] > arr[j])
    {
      *invcnt += (mid - i);
      std::swap(arr[i], arr[j]);
      // rearrange to keep the structure 
      for (int t = j; t > i+1; --t)
      {
        std::swap(arr[t], arr[t-1]);
      }
      ++mid;
      ++j;
    } 
    ++i;
  }
}
 
/// Inplace merge sort the range [beg, end).
void MergeSort(vector<int>& arr, int beg, int end, int* invcnt)
{
  if (end - beg > 1) // need sort
  {
    int mid = (beg + end) / 2;
    MergeSort(arr, beg, mid, invcnt);
    MergeSort(arr, mid, end, invcnt);
    Merge(arr, beg, mid, end, invcnt);
  }
}
} // namespace inplace
 
/// reverse the arr by length k
void ReverseBy(vector<int>& arr, int k)
{
  for (auto beg = arr.begin(); beg != arr.end(); beg += k)
    std::reverse(beg, beg + k);
}
 
/// compute elapsed time from start_time
inline double TimeElapsed(clock_t start_time)
{
  return static_cast<double>(clock()-start_time)
    / CLOCKS_PER_SEC * 1000;
}
 
/// Test wrapper
void UniTest(const vector<int>& numbers, 
             const vector<int>& qs,
             bool inplace)
{
  vector<int> dummynum(numbers);
  vector<int> buffer(numbers.size());
  for (auto e : qs)
  {
    int invcount = 0;
    ReverseBy(dummynum, 1<<e);
    buffer.clear();
    buffer.assign(dummynum.begin(), dummynum.end());
 
    if (inplace)  // use inplace merge sort
      inplace::MergeSort(buffer, 0, buffer.size(), &invcount);
    else
      mergesort(buffer, &invcount);
 
    cout << invcount << endl;
  }
}
 
int main()
{
  // io
  int n;
  cin >> n;
  vector<int> numbers;
  for (int i = 0, tmp = 0; i != (1<<n); ++i)
  {
    cin >> tmp;
    numbers.push_back(tmp);
  }
  int m;
  cin >> m;
  vector<int> qs;
  for (int i = 0, tmp = 0; i != m; ++i)
  {
    cin >> tmp;
    qs.push_back(tmp); 
  }
  // done
 
  clock_t start = clock();
  UniTest(numbers, qs, false);
  cout << TimeElapsed(start) << "ms for mergesort" << endl;
 
  clock_t start2 = clock();
  UniTest(numbers, qs, true);
  cout << TimeElapsed(start2) << "ms for inplace mergesort" << endl;
  return 0;
}

附运行结果，体会一下：

0
6
6
0
0.185ms for mergesort
0
6
6
0
0.068ms for inplace mergesort

差了3倍左右！

基础题

Top K

给定一个无序序列，返回前K小的数。

/******************************************************************************
* File:             topk.cpp
*
* Author:           yychi  
* Created:          2022-12-15 02:04 
* Description:      Find the top k small elements of a sequence.
*****************************************************************************/
 
#include <iostream>
#include <vector>
#include <exception>
 
using std::vector;
 
 
/// The quick sort partition.
size_t partition(vector<int>& arr, size_t beg, size_t end)
{
    size_t pivot = beg;
    size_t i = pivot + 1;
    for (auto j = i; j < end; ++j)
    {
        if (arr[j] < arr[pivot])
        {
            std::swap(arr[i], arr[j]);
            ++i;
        }
    }
    std::swap(arr[pivot], arr[i-1]);
    return i - 1;
}
 
 
/**
 * Return the idx of `k`, with each element left of idx `k`, is smaller
 * than arr[k].
 */
size_t find_idx_of_k(vector<int>& arr, size_t beg, size_t end, size_t k)
{
    size_t mid = partition(arr, beg, end);
    if (mid == k)
    {
        return mid;
    }
    else if (mid < k)
    {
        return find_idx_of_k(arr, mid+1, end, k);
    }
    else
    {
        return find_idx_of_k(arr, beg, mid, k);
    }
}
 
 
vector<int> FindTopK(vector<int>& arr, size_t k)
{
    if (k > arr.size())
    {
        throw std::invalid_argument("");
        return arr;
    }
    if (k == arr.size()) return arr;
    size_t idx = find_idx_of_k(arr, 0, arr.size(), k);
 
    vector<int> ret;
    ret.reserve(idx);
    for (size_t i = 0; i < idx; ++i)
    {
        ret.push_back(arr[i]);
    }
    return ret;
}
 
 
void PrintVector(const vector<int>& arr)
{
    for (auto e : arr) std::cout << e << ' ';
    std::cout << std::endl;
}
 
 
int main()
{
    vector<int> arr {12,234,23423,42,34,2,435,123,5676,8787,9199};
    PrintVector(arr);
    auto ret = FindTopK(arr, 5);
    PrintVector(ret);
    return 0;
}

to be continued…

Learn2Live

探索

排序

排序

题十一：重排并计算逆序数

Top K

关系图谱

目录

反向链接