leetcodes to ponder about.

453. Minimum Moves to Equal Array Elements
268. Missing Number
121. Best Time to Buy and Sell Stock

324

void swap(int *nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

int partition(int *nums, int start, int end) {
    int i = start;
    for (int j = start; j <= end; ++j) {
        if (nums[j] <= nums[end]) {
            swap(nums, i, j);
            i++;
        }
    }
    return i - 1;
}
 
//k starts from 0
int find_kth(int *nums, int start, int end, int k) {
    
    int r = partition(nums, start, end) - start;
    printf("%d-%d-%d-%d\n", start, end, k, r);
    
    if (r == k) {
        return nums[start + k];
    }
    if (r > k) {
        return find_kth(nums, start, r - 1, k);
    } else {
        return find_kth(nums, r + 1, end, k - r - 1);
    }
}
 
void print(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        printf("%d ", nums[i]);
    }
    printf("\n");
}
 
void wiggleSort(int* nums, int numsSize) {
    int mid = (numsSize - 1) / 2;
    int median = find_kth(nums, 0, numsSize - 1, mid);
    
    printf("median = %d\n", median);
    print(nums, numsSize);
    
    //3-way partition
    int i = 0, j = numsSize - 1, k = 0;
    while (k < j) {
        if (nums[k] == median) {
            ++k;
        } else if (nums[k] < median) {
            swap(nums, k, i);
            ++k;
            ++i;
        } else {
            swap(nums, k, j);
            --j;
        }
    }
    
    print(nums, numsSize);
    
    int *result = (int*)malloc(numsSize * sizeof(int));
    
    int r = 0;
    j = numsSize - 1;
    i = median;
    while (j > median) {
        result[r++] = nums[i--];
        result[r++] = nums[j--];
    }
    if (i > 0) {
        result[r++] = nums[i];
    }
    
    return result;
}

发表评论

电子邮件地址不会被公开。