tags: Easy、Sort

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Return the sorted array.

解法1: 快&吃記憶體

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct {
    int num;
    int freq;
} numFreq;

int freqcmp (const void* a, const void* b) {
    numFreq* freqa = (numFreq*)a;
    numFreq* freqb = (numFreq*)b;

    //頻率不等
    if (freqa->freq != freqb->freq) {
        return freqa->freq - freqb->freq;
    }
    else {
        return -(freqa->num - freqb->num);
    }
}

int* frequencySort(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* sort = (int*)calloc(numsSize, sizeof(int));
    int count[201] = {0}; //檢查表
    numFreq array[201];
    //存在這個數字，在檢查表上計算有幾個
    for (int i = 0; i < numsSize; i++) {
        count[nums[i]+100]++; 
    }
    
    for (int i = 0; i < 201; i++) {
        if (count[i] > 0) {
            array[i].num = i - 100;
            array[i].freq = count[i];
        }
    }
    qsort(array, 201, sizeof(numFreq), freqcmp);
    int index = 0;
    for (int i = 0; i < 201; i++) {
        for (int j = 0; j < array[i].freq; j++) {
            sort[index++] = array[i].num;
        }
    }
    return sort;
}

qsort 介紹:
void qsort(void *base, size_t nmemb, size_t size, int(*cmpar) (const void*a, const void* b))

• base：指向要排序陣列的第一個元素的指標。
• nmemb：陣列中的元素個數。
• size：每個元素的大小（以位元組為單位）。
• compar：指向比較函式的指標，用於比較兩個元素。

比較函式:
int cmpar(const void*a, const void* b)

• a和b是要比較的元素的指標。
  返回值:
  返回值為負數(b > a): pointer b 指向的元素在pointer b 指向的元素之後
  返回值為0: pointer a 指向的元素相等pointer b 指向的元素
  返回值為正數(a > b): pointer a 指向的元素在pointer b 指向的元素之後

解法2: 慢&較不吃記憶體

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int count[201];
int freqcmp (const void* a, const void* b) {
    int int_a = *(int*)a;
    int int_b = *(int*)b;

    if (count[int_a+100] != count[int_b+100]) {
        return count[int_a+100] - count[int_b+100];
    } else {
        return int_b - int_a;
    }
}

int* frequencySort(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    for (int i = 0; i < 201; i++) {
        count[i] = 0;
    }

    for (int i = 0; i < numsSize; i++) {
        count[nums[i] + 100]++;
    }

    qsort(nums, numsSize, sizeof(int), freqcmp);
    return nums;
}

1859. Sorting the Sentence

tags: Easy、Sort

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.
A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.
For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".
Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

解法:

typedef struct {
    int seq;
    char token[201];
} Sentence;

char * sortSentence(char * s){
    Sentence sent[201];
    char* token;
    int sequ = 0;
    char* result = (char*)malloc(201 * sizeof(char));
    result[0] = '\0';

    token = strtok(s, " ");
    while (token != NULL) {
        int token_len = strlen(token);
        int token_seq = token[token_len - 1] - '0';
        token[token_len - 1] = '\0';

        sent[sequ].seq = token_seq;
        strcpy(sent[sequ].token, token);
        sequ++;

        token = strtok(NULL, " ");
    }

    for (int i = 0; i < sequ; i++) {
        for (int j = i + 1; j < sequ; j++) {
            if (sent[i].seq > sent[j].seq) {
                Sentence temp = sent[i];
                sent[i] = sent[j];
                sent[j] = temp;
            }
        }
    }

    for (int j = 0; j < sequ; j++) {
        strcat(result, sent[j].token);
        strcat(result, " ");
    }

    if (strlen(result) > 0) {
        result[strlen(result) - 1] = '\0';
    }

    return result;
}

2164. Sort Even and Odd Indices Independently

tags: Easy、Sort

　You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:
Sort the values at odd indices of nums in non-increasing order.
For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.
Sort the values at even indices of nums in non-decreasing order.
For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.
Return the array formed after rearranging the values of nums.

解法:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void bubbleSort(int* array, int size, int flag) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            if((flag && array[j] > array[j+1]) ||
               (!flag && array[j] < array[j+1])) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
            }
        }
    }
}

int* sortEvenOdd(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int evenSize = (numsSize + 1) / 2;
    int oddSize = numsSize / 2;
    
    int* evenArray = (int*)calloc(evenSize, sizeof(int));
    int* oddArray = (int*)calloc(oddSize, sizeof(int));


    for (int i = 0, j = 0; i < numsSize; i+=2, j++) {
        evenArray[j] = nums[i];
    }
    bubbleSort(evenArray, evenSize, 1);

    for (int i = 1, j = 0; i < numsSize; i+=2, j++) {
        oddArray[j] = nums[i];
    }
    bubbleSort(oddArray, oddSize, 0);

    for (int i = 0; i < evenSize; i++) {
        nums[2*i] = evenArray[i];
    }
    for (int i = 0; i < oddSize; i++) {
        nums[2*i + 1] = oddArray[i];
    }

    return nums;
}

2855. Minimum Right Shifts to Sort the Array

tags: Easy、Tree

You are given a 0-indexed array nums of length n containing distinct positive integers. Return the minimum number of right shifts required to sort nums and -1 if this is not possible.
A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

解法1:

bool is_sorted(int* nums, int n) {
    for (int i = 1; i < n; i++) {
        if (nums[i] < nums[i - 1]) {
            return false;
        }
    }
    return true;
}

int minimumRightShifts(int* nums, int numsSize){
    if (is_sorted(nums, numsSize)) {
        return 0;
    }

    // Find the point where the array can be split into two sorted segments
    int shift_point = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < nums[(i - 1 + numsSize) % numsSize]) {
            // Check if the segment starting from this point is sorted
            shift_point = i;
            for (int j = 1; j < numsSize; j++) {
                if (nums[(shift_point + j) % numsSize] < nums[(shift_point + j - 1) % numsSize]) {
                    shift_point = -1;
                    break;
                }
            }
            break;
        }
    }

    if (shift_point == -1) {
        return -1;
    }
    
    return (numsSize - shift_point) % numsSize;
}

解法2:

bool is_sorted(int* nums, int n) {
    for (int i = 1; i < n; i++) {
        if (nums[i] < nums[i - 1]) {
            return false;
        }
    }
    return true;
}

int minimumRightShifts(int* nums, int numsSize){
    if (is_sorted(nums, numsSize)) {
        return 0;
    }

    int shift = -1;
    for (int i = 0; i < numsSize-1; i++) {
        if (nums[i] > nums[i+1]) {
            bool canShift = true;
        
            for (int j = i+1; j <numsSize-1; j++) {
                if(nums[j] > nums[j+1]) {
                    canShift = false;
                    break;
                }
            }

            if (canShift && nums[numsSize-1] <= nums[0]) {
                shift = numsSize - 1 - i;
            }
            break;
        }
    }
    return shift;
}