Kiến thức

Sắp xếp lại mảng theo giá trị tuyệt đối-programming-Dạy Nhau Học

Bạn đang xem: Sắp xếp lại mảng theo giá trị tuyệt đối-programming-Dạy Nhau Học

Sắp xếp lại mảng theo giá trị tuyệt đối

c++

Ý tưởng của em là đưa các giá trị tuyệt đối của x-a[i] vào mảng b[i] rồi sắp xếp nhưng lại không biết đưa các giá trị a[i] ra như thế nào khi đã sắp xếp ở mảng b. Anh chị giúp em với. Nếu có cách khác nhanh hơn thì mách e vs ạ.

#include<iostream> #include<cmath> using namespace std; int n,x,*a,*b; int swap(int &a,int &b) { int x=a; a=b; b=x; } int main() { int T; cin>>T; while(T--) { cin>>n; cin>>x; a=new int[n+1]; for(int i=1;i<=n;i++) { cin>>a[i]; } b=new int[n+1]; for(int i=1;i<=n;i++) { b[i]=abs(x-a[i]); } for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { if(b[i]>b[j]) swap(b[i],b[j]); } } for(int i=1;i<=n;i++) { cout<<b[i]<<" "; } } } 

Chỉ cần 1 mảng a. Khi sắp xếp cho mảng a thì mới tính và so sánh |x - a[i]|.

3 Likes

Bạn có thể tạo một mảng b 2 chiều rồi sau đó lưu lại giá trị cần sắp xếp và giá trị tương ứng ở mảng A.

Ví dụ

A = { 5, -3, 7, 12}; X = 7; 

B[2][4]

|7 - 5| = 2 --> B[0][0] = 2; B[1][0] = 5; |7-(-3)| = 10 --> B[0][1] = 10; B[1][1] = -3; |7 - 7| = 0 --> B[0][2] = 0; B[1][2] = 7; |7 - 12| = 5 --> B[0][3] = 5; B[1][3] = 12; 

Đến lúc sắp xếp và swap thì mình swap luôn 1 cột thay vì chỉ một hàng.

===> B[0][0] = 0; B[1][0] = 7; B[0][1] = 2; B[1][1] = 5; B[0][2] = 5; B[1][2] = 12; B[0][3] = 10; B[1][3] = -3; 

Vậy là sao khi sắp xếp xong bạn vẫn có thể biết được giá trị của phần tử đó ở mảng A là bao nhiêu dựa vào B[1][i]

2 Likes

e tưởng khi tính |x-a[i]| thì cần phải có 1 nơi lưu lại nó rồi mới sắp xếp lại giá trị tuyệt đối chứ ạ

bạn có thể dùng merge sort hoặc quick sort rồi thay điều kiện so sánh thành giá trị tuyệt đối dc mà

def merge(arr, x): left = right = [] if len(arr)>1: mid = len(arr)//2 left = arr[:mid] right = arr[mid:] merge(left, x) merge(right, x) p_left = p_right = p_arr = 0 while p_left<len(left) and p_right<len(right): if abs(x-left[p_left]) < abs(x-right[p_right]): arr[p_arr] = left[p_left] p_left += 1 else: arr[p_arr] = right[p_right] p_right += 1 p_arr += 1 while p_left<len(left): arr[p_arr] = left[p_left] p_left += 1 p_arr += 1 while p_right<len(right): arr[p_arr] = right[p_right] p_right += 1 p_arr += 1 return arr 
1 Like

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button