30/09/2018, 17:05

[Hỏi] Cách lấy vị trí ban đầu của phần tử sau khi đã sắp xếp mảng

Cho em hỏi là em có một mảng trong input, vậy làm sao để lưu lại vị trí của các phần tử đó.

Tình hình là em làm một bài theo trình tự: nhập mảng, sắp xếp lại mảng, tìm kiếm nhị phân, xuất ra vị trí của giá trị vừa tìm được (vị trí ban đầu khi mảng chưa được sắp xếp ấy).

Những cách em nghĩ:

Lưu lại bằng một mảng khác hoàn toàn giống với mảng vừa nhập. Có điều với cách này, cuối cùng cũng phải Linear Search để tìm phần tử => Chậm, với lại nếu vẫn phải Linear thì Binary Search làm gì mắc công
Lùa bò: tạo một mảng copy có số phần tử bằng với giới hạn đề bài. Với input[x] = y thì copy[y] = x (ngược với thằng ở trên). Khi cần tìm vị trí (index) của giá trị y thì cứ lấy thằng copy[y]. => Thằng này hiện đang là tốt nhất, có điều giới hạn của giá trị phần tử mà cỡ 10 mũ 7, 8 thì cũng phải tạo mảng có 10 mũ 7, 8 phần tử => Tốn space.

Vậy mọi người có cách nào tốt hơn không ạ ? Giúp em cái này.

Cám ơn mọi người

Gió viết 19:21 ngày 30/09/2018

Tạo kiểu dữ liệu pair < int,int > trong đó giá trị đầu là giá trị trên mảng, cái sau là chỉ số sau đó sort và search bình thường

nhatlonggunz viết 19:10 ngày 30/09/2018

Anh hướng dẫn chi tiết hơn xíu được không anh. Xài struct ?

... viết 19:08 ngày 30/09/2018

pair cơ bản cũng là struct với 2 template type thôi. Tự tạo struct cho riêng mình cũng được. Khi sắp xếp và tìm kiếm thì dùng với data thôi, còn index giữ nguyên.

Gió viết 19:05 ngày 30/09/2018

Demo:

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> KeyIndex;
KeyIndex arr[100];
int n;
void nhap(){
    cin>>n;
    for(int i=0; i< n;++i){ 
         int x;
         cin>>x;
         arr[i]= KeyIndex(x,i);
    }
    
}

int tim(int key){
      KeyIndex tmp(key, 0);
      KeyIndex * f= lower_bound(arr, arr+n,tmp);
      if(f-> first!= key) return -1;
      return f->second;
}
int main() {
    nhap();
        sort(arr,arr+n);
        cout<<tim(6)<<endl;
        cout<<tim(2)<<endl;
        cout<<tim(5)<<endl;
    return 0;
}