Tìm chỉ số của phần tử bé nhất trong mảng sao cho phần tử đó trong mảng là duy nhất

[chisngyeunptit (Ribi)]

Mọi người cho em hỏi thuật toán tối ưu nhất của bài sau với ạ. Cho mảng a[] gồm n phần tử. Tìm chỉ số của phần tử bé nhất trong mảng sao cho phần tử đó trong mảng là duy nhất.

[SITUVN.gcd]

Vậy thuật toán chưa tối ưu của bạn đâu?

[chisngyeunptit (Ribi)]

Đây ạ:

#include <iostream>
using namespace std;
int main() {
  int test_case;
  cin >> test_case;
  while (test_case--)
  {
    int n,chiso=-1;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++)
    {
      cin >> a[i];
    }
    long long min=1000000000;
    for (int i=0; i<n; i++)
    {
      bool Check=true;
      for (int j=0; j<n; j++)
      {
        if (a[j]==a[i] && j!=i)
        {
          Check=false;
          break;
        }
      }
      if (Check==true && a[i]<min)
      {
        min=a[i];
        chiso=i+1;
      }
    }
    cout << chiso << endl;
  }
  return 0;
}

[rogp10]

• Sắp xếp theo cặp với chỉ số (tốn ít mem hơn)
• Hoặc dùng cây đưa từng phần tử vào.

Theo đề bài thì phải đọc hết mới đưa ra kết luận đúng được, nên dùng cây không thật sự là ưu.

[tntxtnt]

tìm được giá trị phần tử đó rồi tìm vị trí của trị này trong mảng ban đầu là xong, vì nó là duy nhất nên chỉ có 1 vị trí mà :V

template <class T>
size_t minUniqueId(const std::vector<T>& a) {
    auto b = a;
    std::sort(begin(b), end(b));
    auto it = begin(b);
    for (auto jt = it; it != end(b); it = jt) {
        jt = std::find_if(it + 1, end(b), [&](auto& n) { return n > *it; });
        if (std::distance(it, jt) == 1) break;
    }
    return it != end(b) ? std::distance(begin(a), std::find(begin(a), end(a), *it)) : -1;
}