【数据结构初阶】 顺序表三道题，带你见力扣

SeqList Sq;
//相关代码
void SeqListInsert(SeqList* ps, size_t pos, int e)//优美点2
{
	assert(ps);
	assert(pos <= ps->size);//优美点1
	int end = ps->size-1;//优美点2
	while (end >= (int)pos)//优美点2
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = e;
	ps->size++;
}

//错误示范1
void SeqListInsert(SeqList* ps, size_t pos, int e)
{
	assert(ps);
	assert(pos < ps->size);
	size_t end = ps->size-1;
	while (end >= pos)//end为size_t类型时，，如果题目pos给0的话
                      //end (-1)就会转换成一个非常大的数，造成死循环
                        
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = e;
	ps->size++;
}

//错误示范2
void SeqListInsert(SeqList* ps, size_t pos, int e)
{
	assert(ps);
	assert(pos < ps->size);
	int end = ps->size-1;//将end改为int后，在while(int和size_t类型比较的时候)
                         //如果题目pos给0的话
                         //end为-1的时候也会变成size_t，向上提升，造成死循环
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = e;
	ps->size++;
}

//正确做法：在函数内部将pos位置强制转换为int类型，进行比较

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

int removeElement(int* nums, int numsSize, int val){
    if(nums==NULL||numsSize==0)  return 0;
     int j=0;
     for(int i=0;i<numsSize;i++)
     {
         if(nums[i]!=val)
         {
             nums[j++]=nums[i];
         }
 
     }
     return j;
}

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

int removeDuplicates(int* nums, int numsSize){
    
    int j=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[j]!=nums[i])
        {
           nums[++j]=nums[i];
        }
    }
    return j+1;
}

题目描述：
比如：nums1={1,2,5,31,32}  nums2={12,45}
题目给出数组nums1已经使用的长度为m,总长度为nums1Size=m+n，注，这里m<=nums1Size
数组nums2已经使用的长度为n,总长度为numsSize,注，这里n==nums2Size
nums1的总容量nums1Size就是m+n,题目想通过将num2数组里的数据加进num1中，并使得合并后依旧有序

//常规思路：
思路1：先将nums2的内容无脑加进nums1已有元素的后面,然后通过排序使得新的nums1有序
//缺点：时间复杂度高

思路2：开辟一个长度为numsSize（也就是m+n）,然后然后从前往后，不断选小尾插到开辟的数组中
//缺点：返回使就会被题目限制,题目要求只需要将数据给到nums1就可以了

正确做法：nums1和nums2从后往前不断选大,放到nums1的后面（往前）


void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)

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