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

giang3 · November 16, 2019, 9:48am

Ý 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]<<" ";
		}
	}
}

SITUVN.gcd · November 16, 2019, 9:53am

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]|.

sbgssol · November 16, 2019, 10:00am

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]

giang3 · November 16, 2019, 11:32am

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ứ ạ

tungsoul · November 16, 2019, 11:39am

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