1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
// 1122. Relative Sort Array
#include "leetcode.h"
/*
* given two arrays 'arr1' and 'arr2', the elements of 'arr2' are distinct and
* all elements in 'arr2' are also in 'arr1'. sort the elements of 'arr1' such
* that the relative ordering of items in 'arr1' are the same as in 'arr2'.
* elements that do not appear in 'arr2' should be placed at the end of 'arr1'
* in ascending order.
*/
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int *relativeSortArray(int *arr1, int arr1Size, int *arr2, int arr2Size,
int *returnSize) {
int cnt = 0;
for (int i = 0; i < arr2Size; i++)
for (int j = 0; j < arr1Size; j++)
if (arr1[j] == arr2[i])
swap(&arr1[j], &arr1[cnt++]);
for (int i = cnt; i < arr1Size; i++) {
int min = arr1[i], idx = i;
for (int j = i + 1; j < arr1Size; j++)
if (arr1[j] < min)
min = arr1[j], idx = j;
swap(&arr1[i], &arr1[idx]);
};
*returnSize = arr1Size;
return arr1;
}
int main() {
int a11[] = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}, a21[] = {2, 1, 4, 3, 9, 6},
a12[] = {28, 6, 22, 8, 44, 17}, a22[] = {22, 28, 8, 6}, rs1, rs2;
int *rsa1 =
relativeSortArray(a11, ARRAY_SIZE(a11), a21, ARRAY_SIZE(a21), &rs1);
int *rsa2 =
relativeSortArray(a12, ARRAY_SIZE(a12), a22, ARRAY_SIZE(a22), &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", rsa1[i]); // expect: 2,2,2,1,4,3,3,9,6,7,19
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", rsa2[i]); // expect: 22,28,8,6,17,44
printf("\n");
free(rsa1), free(rsa2);
}
|