配列のコーディングに関する問題をC++で解いてみた

# はじめに
[ネットで見かけた問題](https://postd.cc/50-data-structure-and-algorithms-interview-questions-for-programmers/)が面白そうでとこうと思い、解き始めました。せっかく解いたので、問題の紹介も兼ねて記事にすることにしました。

全ての問題を解き終わってからまとめようと思ったのですが、時間がかかりそうだったので、見出しで一旦まとめることにしました。

# 問題
[こちら](https://postd.cc/50-data-structure-and-algorithms-interview-questions-for-programmers/)にある50問のうち、大問１(配列のコーディングに関する質問)を解いた。リンク先は[海外のページ](https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0)の和訳とのこと。
少し問題の解釈が曖昧なところはあるが、おおまかにはできた。

# Q1.不足する数値を探す
与えられた配列をソートして、前から順に値を確認し、差が１でない（不足する数値は１つのようなので２である）場合、その数値が不足する数値である。

```cpp:q1.cpp
#include <iostream>
#include <vector>
using namespace std;
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
template<typename T> void view(const T e){ std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T>>& vv){ for(const auto& v : vv){ view(v); } }

vector<int> genVector(int size){
  vector<int> v(size);
  for(size_t i=0; i<size; ++i){
    v[i] = i;
  }
  return v;
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVector(100);
  v.erase(v.begin()+50);
  sort(v.begin(), v.end());
  for(size_t i=1; i<v.size(); ++i){
    if(v[i-1]!=v[i]-1){
      cout << "Nothing number : " << v[i] << endl;
      return i;
    }
  }
  cout << "all number existing!" << endl;
  return 0;
}
```
# Q2.重複する数値を探す
Q1と近い方法で解決した。与えられた配列をソートして、前から順に値を確認し、前後が同値である場合、その数値が重複する数値である。

```cpp:q2.cpp
#include <iostream>
#include <vector>

using namespace std;
template<typename T> void view(const T e){ std::cout << e << std::endl;}
template<typename T> void view(const vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }
template<typename T> void view(const vector<vector<T>>& vv){ for(const auto& v : vv){ view(v); } }

vector<int> genVector(int size){
  vector<int> v(size);
  for(size_t i=0; i<size; ++i){
    v[i] = i;
  }
  return v;
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVector(100);
  v.push_back(49);
  sort(v.begin(), v.end());
  for(size_t i=1; i<v.size(); ++i){
    if(v[i-1]==v[i]){
      cout << "Duplicate number : " << v[i] << endl;
      return i;
    }
  }
  cout << "Nothing duplicate number!" << endl;
  return 0;
}
```
# Q3.最大値と最小値を探す
配列を走査し、`maximum`と`minimum`を更新することで、最大値と最小値を得る。

```cpp:q3.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>

using namespace std;
int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(10);
  debug(v);
  int minNum = v[0];
  int maxNum = v[0];
  for(const auto& e : v){
    minNum = min(minNum, e);
    maxNum = max(maxNum, e);
  }
  cout << "max number : " << maxNum << endl;
  cout << "min number : " << minNum << endl;
  return 0;
}
```

```cpp:template.hpp
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)

#ifndef _CPP_VECTOR
#include <vector>
#endif
#ifndef _CPP_MAP
#include <map>
#endif
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> void view(const T e){ std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }
template<typename T> void view(const VV<T>& vv){ for(const auto& v : vv){ view(v); } }
template<typename T1, typename T2> void view(const std::pair<T1,T2> e){ std::cout << "(" << e.first << ", " << e.second << ")" << std::endl;}
template<typename T1, typename T2> void view(const std::vector<std::pair<T1,T2>>& v){ for(const auto& e : v) std::cout << "(" << e.first << ", " << e.second << ") "; std::cout << std::endl; }
template<typename T1, typename T2> void view(const std::map<T1,T2>& v){ for(const auto& e : v) std::cout << "(" << e.first << ", " << e.second << ") "; std::cout << std::endl; }
template<class Iterator> void view(const Iterator& begin, const Iterator& end){ for(auto itr=begin; itr!=end; itr++) std::cout << *itr << " "; std::cout << std::endl; }
```

```cpp:genVector.hpp
#ifndef _CPP_VECTOR
#include <vector>
#endif

#ifndef _CPP_RANDOM
#include <random>
#endif

std::vector<int> genVectorByOrder(size_t size){
  std::vector<int> v(size);
  for(size_t i=0; i<size; ++i){
    v[i] = i;
  }
  return v;
}

std::vector<int> genVectorByRandom(size_t size){
  std::mt19937 mt{ std::random_device{}() };
  std::uniform_int_distribution<int> rnd(0, 100);
  std::vector<int> v(size);
  for(size_t i=0; i<size; ++i){
    v[i] = rnd(mt);
  }
  return v;
}

std::vector<int> genVectorByRandom(size_t size, int rndMax){
  std::mt19937 mt{ std::random_device{}() };
  std::uniform_int_distribution<int> rnd(0, rndMax);
  std::vector<int> v(size);
  for(size_t i=0; i<size; ++i){
    v[i] = rnd(mt);
  }
  return v;
}
```

# Q4.配列と数値が与えられ、配列のうち和がその数値となるペアを探す
配列をソートして、両端から探索することにした。ペアの和が与えられた数値`givenNumber`
- と等しい場合はその数値を解に追加
- より小さい場合はペアのうち大きい方を左へ移動
- より大きい場合はペアのうち小さい方を右へ移動
とした。

```cpp:q4.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>

constexpr size_t arSize = 50;
constexpr long givenNumber = 50;

using namespace std;
int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize);
  sort(v.begin(), v.end());
  debug(v);
  vector<pair<size_t,size_t>> pairs;
  size_t lower = 0;
  size_t upper = arSize-1;
  bool upFlag = false;
  bool downFlag = false;
  while(lower!=upper){
    long sumOfTwo = v[lower] + v[upper];
    if(sumOfTwo==givenNumber){
      pairs.emplace_back(v[lower], v[upper]);
      if(v[lower+1]+v[upper] == givenNumber && !upFlag){
        pairs.emplace_back(v[lower+1], v[upper]);
        upFlag = true;
      }else if(v[lower]+v[upper-1] == givenNumber && !downFlag){
        pairs.emplace_back(v[lower], v[upper-1]);
        downFlag = true;
      }else{
        upFlag = false;
        downFlag = false;
        lower++;
      }
    }else if(sumOfTwo<givenNumber){
      lower++;
    }else if(sumOfTwo>givenNumber){
      upper--;
    }
  }
  cout << "pattern of sum : " << pairs.size() << endl;
  view(pairs);
  return 0;
}
```
# Q5.複数の重複がある配列から重複する数値を探索
Q2同様、ソートして下から走査していった。ここでは、複数の重複があるということで、一つ隣が同値であればその隣、さらに同値であればさらにその隣、、、と比較することにした。

```cpp:q5.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>

constexpr size_t arSize = 50;
constexpr int rndMax = 100;

using namespace std;
int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  sort(v.begin(), v.end());
  view(v);
  vector<int> duplicate;
  size_t i, j;
  for(i=0; i<v.size()-1; ++i){
    for(j=i; v[i]==v[j]; ++j){}
    if(v[i] == v[i+1]) duplicate.push_back(v[i]);
    i = j - 1;
  }
  view(duplicate);
  return 0;
}
```
# Q6.配列から重複を削除
実際の問題では`Javaにおいて`とあるが、C++でやることにした。

```cpp:q6.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>

constexpr size_t arSize = 50;
constexpr int rndMax = 100;

using namespace std;
int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  view(v);
  auto vTemp = v;
  sort(vTemp.begin(), vTemp.end());
  map<int, int> duplicateMap;
  size_t i, j;
  for(i=0; i<vTemp.size()-1; ++i){
    for(j=i; vTemp[i]==vTemp[j]; ++j){}
    if(vTemp[i] == vTemp[i+1]) duplicateMap.emplace(vTemp[i], j-i);
    i = j - 1;
  }
  for(auto& e : duplicateMap) e.second = e.second - 1;
  for(i=v.size()-1; i<v.size(); --i){
    auto itr = duplicateMap.find(v[i]);
    if(itr!=duplicateMap.end()){
      if(duplicateMap[v[i]]!=0){
        duplicateMap[v[i]] = duplicateMap[v[i]]-1;
        v.erase(v.begin()+i);
      }
    }
  }
  cout << "duplicate number was erased!" << endl;
  view(v);
  return 0;
}
```
# Q7.クイックソートの実装
配列の要素で実装しても良いのだが、以前他の記事のコメントで、「イテレータを使うと勉強になるよ」という言葉をいただいたので、この問題は２パターンの関数を作成した。

```cpp:q7.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>
using namespace std;

constexpr size_t arSize = 50;
constexpr int rndMax = 100;

template<typename T> void quickSort(std::vector<T>& v, const int left, const int right){
  if(right - left < 1) return ;
  auto central = v[(right-left)/2];
  auto pivot = central;
  if(v[left]<v[right]){
    if(v[left]<central){
      if(central<v[right]){
      }else{
        pivot = v[right];
      }
    }else{
      pivot = v[left];
    }
  }else{
    if(central<v[right]){
      pivot = v[right];
    }else{
      if(v[left]<central){
        pivot = v[left];
      }else{
      }
    }
  }
  int i = left, j = right;
  while(1){
    while(v[i]<pivot) i++;
    while(pivot<v[j]) j--;
    if(i >= j) break;
    swap(v[i],v[j]);
    i++;
    j--;
  }
  if(right - left < 2) return ;
  quickSort(v, left, i-1);
  quickSort(v, j+1, right);
}

template<class Iterator> void quickSort(const Iterator& begin, const Iterator& end){
  if(end - begin < 2 ) return;
  auto left = begin;
  auto right = end-1;
  auto central = left + distance(left, right)/2;
  auto pivot = *central;
  if(*left<*right){
    if(*left<*central){
      if(*central>*right){
        pivot = *right;
      }
    }else{
      pivot = *left;
    }
  }else{
    if(*central<*right){
      pivot = *right;
    }else{
      if(*left<*central){
        pivot = *left;
      }else{
      }
    }
  }
  auto i = left;
  auto j = right;
  while(1){
    while(*i<pivot) i++;
    while(pivot<*j) j--;
    if(i >= j) break;
    iter_swap(i,j);
    i++;
    j--;
  }
  if(end - begin <= 2) return ;
  if(i-begin>1)quickSort(begin, i);
  if(end-j>1)quickSort(j+1, end);
}

template<typename T> bool alignmentCheck(vector<T>& v){
  bool alignment = true;
  for(size_t i=1; i<v.size(); ++i){
    if(v[i-1]>v[i]) alignment = false;
  }
  return alignment;
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  view(v);
  cout << (alignmentCheck(v)? "OK" : "NG" ) << endl;
  auto vTemp = v;
  quickSort(vTemp, 0, vTemp.size()-1);
  view(vTemp);
  cout << (alignmentCheck(vTemp)? "OK" : "NG" ) << endl;
  vTemp = v;
  quickSort(vTemp.begin(), vTemp.end());
  view(vTemp);
  cout << (alignmentCheck(vTemp)? "OK" : "NG" ) << endl;

  return 0;
}
```
# Q8.配列から重複を削除
問題からのリンク先を見ると、削除とは値を0にすることのようなので、ここでもそれを行った。

```cpp:q8.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>
using namespace std;

constexpr size_t arSize = 10;
constexpr int rndMax = 10;

template <typename T> void duplicateTo0 (vector<T>& v){
  size_t i, j;
  for(i=0; i<v.size(); ++i){
    for(j=i+1; j<v.size() && v[i]==v[j]; ++j){
      v[j] = 0;
    }
    i = j - 1;
  }
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  view(v);
  sort(v.begin(), v.end());
  view(v);
  duplicateTo0(v);
  view(v);
  return 0;
}
```
# Q9.配列を反転
```cpp:q9.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>
using namespace std;

constexpr size_t arSize = 10;
constexpr int rndMax = 10;

template <typename T> void reverse (vector<T>& v){
  for(size_t i=0; i<v.size()/2; ++i){
    swap(v[i], v[v.size()-1-i]);
  }
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  view(v);
  reverse(v);
  view(v);

  return 0;
}
```
# Q10.ライブラリを使わないで配列から重複を削除
「ライブラリを使わないで」とあるが、問題の解答例では昇順に並んでいる配列が与えられていたため、配列の生成とソートまではそのまま使うことにした。プログラムはQ8と一緒になってしまった。

```cpp:q10.cpp
#include <iostream>
#include <vector>

#include <genVector.hpp>
#include <template.hpp>
using namespace std;

constexpr size_t arSize = 10;
constexpr int rndMax = 10;

template <typename T> void duplicateTo0 (vector<T>& v){
  size_t i, j;
  for(i=0; i<v.size(); ++i){
    for(j=i+1; j<v.size() && v[i]==v[j]; ++j){
      v[j] = 0;
    }
    i = j - 1;
  }
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  view(v);
  sort(v.begin(), v.end());
  view(v);
  duplicateTo0(v);
  view(v);

  return 0;
}
```

# おわりに
今回は大問１の配列に関する問題だけをまとめました。続きの問題も少しづつ解いていけたらと思っています！