【C语言练习】数组OJ题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C语言练习】数组OJ题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.消失的数字

题目：
【C语言练习】数组OJ题,c语言,算法,数据结构

思路1：

数组是从0加到N，所以把0到N的数加起来减去数组中的值，结果就是消失的数字。时间复杂度为O(N)
代码：

int missingNumber(int* nums, int numsSize)
{
    int ret = (numsSize+1)*numsSize/2;//0到N的数相加
    int i=0;
    for(i=0;i<numsSize;i++)
    {
        ret-=nums[i];//减去数组中的值
    }
    return ret;//消失的数字
}

思路2：

采用单身狗思路（异或法）
从0到N的值是依次加1，数组中消失的数字唯一出现一次，其他的数字都是成对出现
代码：

int missingNumber(int* nums, int numsSize)
{
    int x=0;
    int i=0;
    for(i=0;i<=numsSize;i++)
    {
        x^=i;
    }
    for(i=0;i<numsSize;i++)
    {
        x^=nums[i];
    }
    return x;
}

二.移除元素

题目：
【C语言练习】数组OJ题,c语言,算法,数据结构
创建两个变量src和dest，让src去遍历数组（src的范围小于元素个数），如果数组中的元素与val相等，就跳过；否则赋给dest，然后两个再一起到下一个元素。src遍历完返回dest就是数组的新长度。
代码：

int removeElement(int* nums, int numsSize, int val)
{
    int dest = 0;
    int src = 0;
    while(src<numsSize)
    {
        if(val==nums[src])
        {
            src++;
        }
        else
        {
            nums[dest]=nums[src];
            dest++;
            src++;
        }
    }
    return dest;
}

三.轮转数组

题目：
【C语言练习】数组OJ题,c语言,算法,数据结构
构建一个逆置的函数（注意传参时参数要对应清楚）

1 2 3 4 5 6 7 原来的数组
7 6 5 4 3 2 1 先全部逆置
5 6 7 1 2 3 4 后逆置左边k个，右边numsSize-k个
得到的就是右轮转k个的数组

如果k大于numsSize，可以取模操作，除去重复的工作，效率更高

代码：

void test(int* nums,int left, int right)
{
   while(left<right)
   {
       int t=nums[left];
       nums[left]=nums[right];
       nums[right]=t;
       left++;
       right--;
   }
}
void rotate(int* nums, int numsSize, int k)
{
    if(k>numsSize)//除去重复操作
    {
        k%=numsSize;
    }
    test(nums,0,numsSize-1);//全部逆置
    test(nums,0,k-1);//逆置左边3个
    test(nums,k,numsSize-1);//逆置右边4个
    int i=0;
    for(i=0;i<numsSize-1;i++)
    {
        printf("%d,",nums[i]);
    }
}

四.删除有序数组中的重复项

题目：
【C语言练习】数组OJ题,c语言,算法,数据结构
先存放数组的第一个元素，然后定义一个遍历去遍历数组，只要是重复的数字就跳过，不重复就存放到数组中，每次存放有一个变量（k）加1，（比较的是当前遍历到的数组中的某个元素与前面刚存放到数组的元素）直到遍历完返回k+1（数组新长度的值）

代码：

int removeDuplicates(int* nums, int numsSize)
{
    int src = 0;
    int k=0;
    nums[k]=nums[src];
    src++;
    while(src<numsSize)
    {
        if(nums[src]==nums[k])
        {
            src++;
        }
        else
        {
            k++;
            nums[k]=nums[src];
            src++;
        }
    }
    return k+1;
}

五.合并两个有序数组

题目：
【C语言练习】数组OJ题,c语言,算法,数据结构
注意：这题的要求有一点不一样，合并后的数组不是在函数里又创建一个，而是存储到nums1去。

所以这题可以使用一种方法：倒着比较，取大的依次往前插入
当某个数组的全部放完了，直接把另一个数组依次往前插入就行（如果是num1还有元素没放完就不需要，因为num1就是它自己，num2有多余的元素需要有这个条件）

代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int end1=m-1;
    int end2=n-1;
    int end = m+n-1;
    while(end1>=0&&end2>=0)
    {
        if(nums1[end1]>nums2[end2])
        {
            nums1[end--]=nums1[end1--];
        }
        else
        {
            nums1[end--]=nums2[end2--];
        }
    }
    while(end2>=0)
    {
        nums1[end--]=nums2[end2--];
    }
}