aboutsummaryrefslogtreecommitdiff
path: root/relative_sort_array.c
blob: fa997c3aa33b19f27eee94ec51ef9b8d7b333499 (plain)
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);
}