C程序设计语言--使用GCC(11)

    数据结构决定算法！这两天在学习数据结构与算法，就下面两道算法题，给出自己的代码：

    1，给定N个随机数，求第k个数是多少。当N等于1000000，k等于500000时。我是采用了位图法，先生成一个测试用的随机数数组，个数有100万个，其中的元素取值范围为1-1000000之间。输出是经排序后的第50万个元素。值得注意的是，100万个元素的数组只能在main函数外部定义。

#include <stdio.h>
unsigned long next1 = 2;
unsigned int input[1000000];
unsigned int temp[1000000];
int main()
{

    unsigned long i;
    unsigned long j;

    for(i=0; i<1000000; i++) {
        input[i] = rand1();
        temp[i] = 0;
    }

    for(i=0; i<1000000; i++) {
        j = input[i];
        temp[j]++;
    }

    j = 0;
    for(i=0; j<500000; i++) {
        j += temp[i];
    }
    printf("%u",i);

//    for(i=0; i<1000000; i++)
//        printf("%u ",temp[i]);
    return 0;
}

int rand1(void)
{
    next1 = next1 * 1103515245 + 12345;
    return (unsigned int)(next1/200) % 1000000;
}

    2，对一个长度为LENGTH的向量，向左旋转NUM个位置。要求是只能用一个中间向量，并且时间要跟LENGTH成正比。我是使用了一个中间数组，对原左边进行一次反转，再对右边进行一次反转，最后对整个中间数组，进行反转。

#include <stdio.h>
#define LENGTH 8
#define NUM 3

int main()
{
    char input[] = {"abcdefgh"};
    char temp[100];
    int i, j;
    printf("%s\n",input);

    for(i=NUM-1, j=0; i>=0; i--, j++)
        temp[j] = input[i];
    for(i=LENGTH-1, j=NUM; i>=NUM; i--, j++)
        temp[j] = input[i];
    for(i=LENGTH-1, j=0; i>=0; i--, j++)
        input[j] = temp[i];
    printf("%s\n",input);
    return 0;
}