[数据结构与算法]《九国列车》（学习报告）《leecode零基础指南》(第7天) ——排序，对排序的处理及题解和错题的总结

1.leetcode.912--排序数组

我们先来看一种不对的做法

int *sortArry(int *nums,int numsSize,int *returnSize)//函数的*int型，返回的是数组的首地址
{
int *jie=(int *)malloc( sizeof(int） * numsSize);//动态开辟内存空间，搞一个长度为numsSize的数组，首地址为Jie
int i=0,j=0,t=0;
//使用冒泡将数组升序排列
for(i=0;i<numsSize;i++)
{
for(j=0;j<numsSize;j++)
{
if(nums[j]>nums[j+1])
{
t=nums[j];
nums[j]=nums[j+1];
nums[j+1]=t;
}
}
}
//填充数组元素到Jie中
for(i=0;i<numsSize;i++)
{
jie[i]=nums[i];
}
*returnSize=numsSize;//老样子，我们还要告诉调用者数组的长度，一般用一个参数*returnSize实现
return jie;//返回首地址
}

• 提交后会显示超出时间限制，最后几个案例有成千上万个数值，速率过慢?
• 插入，冒泡，选择都不可以
• 在这里我边水题边学，去学习了一下希尔排序

int *sortArry(int *nums,int numsSize,int *returnSize)
{
int i=0,j=0,t=0,k,m;
for(m=numsSize/2;m>0;m=m/2)//设置增量，一般可以理解为分组的数据的间隔，第一次一般都是长度的一半。后面每一次都是原来增量的1/2
{
for(k=m;k<numsSize;k++)
{
t=nums[k];//将插入的数存给t
j=k-m;
while(j>=0&&t<nums[j])//若t比前面的数字小，前面的数据前移
{
nums[j+m]=nums[j];
j=j-m;
}
nums[j+m]=t;//注意这里和j=j-k和j=j-m的联系，需要思考
}
}
*returnSize=numsSize;//老规矩，我们一般用一个参数来实现告诉调用者数组的长度
return nums;
}

• 
• 2.leetcode.169--多数元素
• 下面来看一种错误的做法
• ?

?

int jie(int *nums,int numsSize)
{
int a=0,i=0,j=0;
for(i=0;i<numsSize;i++)
{
int a=0;
for(j=0;i<numsSize;j++)
{
if(nums[i]==nums[j]
{
a++;//判断重复次数
}
}
if(a>numsSize/2)
{
return nums[i];//因为重复次数大于numsSize/2的数只有一个，所以可以直接返回一个

}
}
return 0;
}

• 但是这样做会显示超出时间限制┭┮﹏┭┮
• 主要是对题目的思考不到位，应该用排序的思想来得出满足条件的元素的位置

• class Solution {
   public boolean jie(int [] nums)
  {
    int i=0,j=0;
  Arrays.sort(nums);//先排序，方便接下来和前一位进行比较
  
  for(i=1;i<nums.length;i++)//注意这里是从1开始，如果从0开始，下面公式弄成nums[i]==nums[i+1]是不可以的。
  {
  if(nums[i]==nums[i-1])
  return true;
  }
  return false;
  }
  }
  

  感谢这位优秀的题解https://leetcode-cn.com/problems/majority-element/solution/169-duo-shu-yuan-su-by-chen-wei-f-imuv/

3.leetcode.217--存在重复元素

4.leetcode.164--最大间距

?

• 这道题如果不是英雄哥推出的打卡题，我看到它为困难的难度会直接被劝退，但是去写了一下发现萌新都是可以写的

?下面我们来看代码

class solution{
public int jie(int [] nums)
{
Arrays.sort(nums);
int max=0;//初始化一个值，用来和后面得到相邻元素的差值进行比较，如果max小的话，将其赋给max
int i=0,j=0;//初始化一个j用来储存差值
if(nums.length<2)//题目要求，按要求来即可
return 0;
else
{
for(i=1;i<nums.length;i++)
{
j=nums[i]-nums[i-1];
if(max<j)
max=j;
}
return max;
}

}
}

• 总结：以上英雄哥推出的打卡题都有许多相似之处，非常适合像只有语言基础的萌新去练习和总结，遇到不会的可以去翻看视频，做好笔记，边水题边学。?
• 今天是九日集训———雪国列车leetcode萌新零基础打卡指南第7天，不管再忙，明天也要打卡和总结哦！
• 天道酬勤，勤能补拙，萌新们，加油！

?

?

?