论述题1. 在一个数组中,只有一个数出现了m次,其他的数都出现了n次,求出现m次的那个数。
采用蛮力法,遍历查找每个数字出现的次数,同时开辟空间将每个数字出现的次数记录下来,最终遍历结果,即可找出出现m次的那个数。实现代码如下:
class Test
{
public static int FindSingleNumber(int[] nums, int m, int n)
{
Dictionary<int, int>dict=new Dictionary<int, int>();
for(int i=0;i<nums,Length; i++)
{
if (dict.ContainsKey(nums[i]))
{
//如果数字已经存在,则更新存在次数
dict[nums[i]]=dict[nums[i]]+1;
}
else
{
//数字不存在则添加到字典中
dict.Add(nums[i],1);
}
}
foreach (var item in dict)
{
if(item.Value==m)
{
return item.Key;
}
}
return 0;
}
static void Main()
{
int m=2;
int n=3;
int[] array={1,2,3,4,1,2,3,4,1,2,3};
Console.Write(FindSingleNumber(array,m,n));
Console.Read();
}
}
程序的运行结果为:
4
算法性能分析:
整个算法只需要对原来的数组扫描一次,所以时间复杂度为O(n),因为申请了一个字典存储变量,所以空间复杂度为O(n)。
[考点] 如何求解n-m问题
2. 如何求2个有序数组合并后的中位数?
最简单的办法就是把两个数组合并、排序,然后返回中位数即可,由于两个数组原本是有序的,因此可以用归并排序中的merge步骤合并两个数组。由于题目只要求返回中位数,因此并不需要真的合并两个数组,只需要模拟合并两个数组的过程即可:每次选数组中较小的数,统计到第(x+y+1)/2个元素就是要找的中位数。此种算法的时间复杂度为O(X+y)。
除此以外,还有更为高效的二分法思想可供使用,首先比较数组x,y的中间元素x[n/2],y[n/2],二者的比较结果可以分为以下几种情况:
1)如果x[n/2]==y[n/2],那么说明x[n/2]就是第n大的数,也就是那个中位数。
2)如果x[n/2]>y[n/2],那么说明y[0]-y[n/2]之间的n/2个数肯定在前n个数当中,而且中位数一定在x数组的前半部分或者y数组的后半部分,只要转换成在x数组的前半部分和y数组的后半部分找到第(n-n/2)大的元素,即可以递归求解。
3)如果x[mid]<y[mid],那么分析同上。
根据以上思路的实现代码如下:
class Test
{
public static int FindMedian(int[] a, int n1, int[] b, int n2)
{
int m1=(n1-1)/2,m2=(n2-1)/2;
if(n1==1)
{//递归结束条件
if(n2==1)
return a[0]<b[0]? a[0]:b[0];
if(n2%2==0)
{
if(a[0]>=b[m2+1])
return b[m2+1];
else if(a[0]<=b[m2])
return b[m2];
else return a[0];
}
else
{
if(a[0]>=b[m2])
return b[m2];
else if (a[0]<=b[m2-1])
return b[m2-1];
else return a[0];
}
}
else if(n2==1)
{//递归结束条件
if(n1 %2==0)
{
if(b[0]>=a[m1+1])
return a[m1+1];
else if (b[0]<=a[m1])
return a[m1];
else return b[0];
}
else
{
if(b[0]>=a[m1])
return a[m1];
else if(b[0]<=a[m1-1])
return a[m1-1];
else return b[0];
}
}
else
{
int cutLen=n1/2>n2/2?n2/2:n1/2;
//注意每次减去短数组的一半, 如果数组长度n是奇数, 一半是指(n-1)/2
if(a[m1]==b[m2])return a[m1];
else if(a[m1]<b[m2])
{
int[] temp=new int[n1-cutLen];
Array.Copy(a, cutLen, temp,0, n1-cutLen);
return FindMedian(temp, n1-cutLen, b, n2-cutLen);
}
else
{
int[] temp=new int[n2-cutLen];
Array.Copy(b, cutLen, temp, 0, n2-cutLen);
return FindMedian(a, n1-cutLen, temp, n2-cutLen);
}
}
}
public static void Main(strin[] args)
{
int[] a=new int[] {1, 2, 3, 4};
int[] b=new int[] {5, 6, 7, 8, 9};
Console.Write(FindMedian(a, a.Length, b, b.Length));
Console.Read();
}
}
程序的运行结果为 :
5
算法性能分析:
因为采用了二分法,所以时间复杂度为O(1og2n),空间复杂度为o(n)。
[考点] 如何求2个有序数组合并后的中位数
3. 输入n个整数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。
最容易想到的方法就是先将数组排序,然后输出前k个数字即可,对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。本题可以采用快速排序或堆排序来实现。
可以试着进行算法的优化,快速排序算法可以提供启发,如果基于数组的第k个数字来调整,那么可以使得比第k个数字小的所有数字位于数组的左边,比第k个数字大的所有数字位于数组的右边。这样调整后,位于数组左边的k个数字就是最小的k个数字(这k个数字不一定是排序的)。基于这个思路,算法复杂度降为了O(n)。
下面给出优化后的代码:
class Test
{
public static void GetLeastNumbers(int[] input, int k)
{
if(input.Length==0||k>input.Length||k<=0)
{
Console.WriteLine("无法找到符合条件的数据!");
}
int low=0;
int high=input.Length-1;
int index=Partition(input, k, low, high);
while(index!=k-1)
{
if(index>k-1)
{
high=index-1;
index=Partition(input, k, low, high);
}
else
{
low=index+1;
index=Partition(input, k, low, high);
}
}
for (int i=0; i<k; i++)
{
Console.Write(input[i].ToString()+"");
}
}
static int Partition(int[] input, int k, int low, int high)
{
int pivotkey=input[k-1];
Swap(input, k-1, low);
while(low<high)
{
while (low<high && input[high]>=pivotkey)
{
high--;
}
Swap(input, low, high);
while(low<high && input[low]<=pivotkey)
{
low++;
}
Swap(input, low, high);
}
return low;
}
static void Swap(int[] input, int low, int high)
{
int temp=input[high];
input[high]=input[low];
input[low]=temp;
}
public static void Main(string[] args)
{
GetLeastNumbers(new int[] {4, 5, 1, 6, 2, 7, 3, 8}, 4);
Console.Read();
}
}
程序的运行结果为:
2 3 1 4
算法性能分析:
在解题思路中,已经对算法的时间复杂度进行了分析,第二种算法的时间复杂度最低为O(n)。
[考点] 如何找出n个整数中最小的k个数
4. 有一个数组A,对于数组下标i和j,如果i<j,并且A[i]>A[j],则称(A[i],A [j])是一个逆序对,请求解数组A中一共有多少个逆序对。
第一种解法是顺序扫描整个数组,每一个数都和它后面的数作比较。但这种解法需要O(n2)的时间复杂度。
那有没有时间复杂度更低的解法呢?当然有,当针对数组遍历求符合条件的数据时,可以采用分治的思想,针对本题,可以按照如下步骤来求解:
1)把数组分隔成子数组;
2)先统计出子数组内部的逆序对数目;
3)再统计两个相邻子数组之间的逆序对数目;
在统计逆序的过程中,同时对数组进行归并排序。
实现代码如下:
class Test
{
static int count=0;
static long ReversePairs(int[] array)
{
if (array,Length<=1)return 0;
Merge(array, 0, array.Length-1);
return count;
}
static int[] Merge(int[] array, int start, int end)
{
if (start==end)
{
return new int[]{array[start]};
}
int mid=(start+end)/2;
int[] a1=Merge(array, start, mid);
int[] a2=Merge(array, mid+1,end);
int i=a1.Length-1;
int j=a2.Length-1;
int k=a1.Length+a2.Length-1;
int[] sort=new int[a1.Length+a2.Length];
while(i>=0&&j>=0)
{
if(a1[i]>a2[j])
{
count+=(j+1);
sort[k--]=a1[i--];
}
else
{
sort[k--]=a2[j--];
}
}
while(i>=0)
{
sort[k--]=a1[i--];
}
while(j>=0)
{
sort[k--]=a2[j--];
}
return sort;
}
public static void Main(string[] args)
{
Console.Write(ReversePairs(new int[]{4,5,1,6,2,7,3,8}));
Console.Read();
}
}
程序的运行结果为:
9
算法性能分析:
由于采用分治和归并的思想,因此本题的时间复杂度为O(nlog2n)。
[考点] 如何求解数组中逆序对的个数
5. 给出一个整数数组A[n],其具有以下特点:
1)相邻位置的数字是不同的;
2)A[0]<A[1],并且A[n-2]>A[n-1];
假定P是峰值的位置,则满足A[P]>A[P-1]且A[P]>[P+1],返回数组中任意一个峰值的位置。需要注意的是,数组可能包含多个峰值,只需找到其中的任何一个即可。例如数组[1,2,1,3,4,5,7,6]返回1,即数值2所在位置,或者6,即数值7所在位置。
本题主要考察读者阅读理解的能力,理解题意之后很容易写出代码,遍历一遍数组即可。书中多次提到过,针对数组中求符合条件的数值,可以采用分治的方法来降低时间复杂度,本题也可以采用分治的思想:如果中间元素大于其相邻后续元素,那么中间元素左侧(包含该中间元素)必包含一个局部最大值。如果中间元素小于其相邻后续元素,那么中间元素右侧必包含一个局部最大值。
下面给出优化后的代码:
class Test
{
static int? FindPeakElement(int[] num)
{
int left=0,right=num.Length-1;
while(left<=right)
{
if(left==right)
{
return left;
}
int mid=(left+right)/2;
if(num[mid]<num[mid+1])
{
left=mid+1;
}
else
{
right=mid;
}
}
return null;
}
public static void Main(string[] args)
{
Console.WriteLine(FindPeakElement(new int[]{1,2,1,3,4,5,7,6}));
Console.Read();
}
}
程序的运行结果为:
6
算法性能分析:
采用分治后代码的时间复杂度为O(log2n),空间复杂度为O(l)。
[考点] 如何找出数组的峰值
6. 给定一个数组,找出这个数组的—个连续子集,这个子集中所有数的乘积最大。例如,给定数组[2,3,-2,4],这个连续的子集为[2,3],这个子集中所有数字的乘积为6。
解法一:首先穷举所有子数组,然后再计算出最大乘积即可。
解法二:本题和连续予数组最大和的问题是一类问题,都可以用动态规划来求解,前面的题目中已经介绍过动态规划的方法,这里不再赘述。
因为数组中存在正、负、零的情况,为了处理数组元素为负的问题,必须将最小乘积也保存起来。鉴于此,可以有这样的结论,如果当前元素a[i]为负数,那么a[i]*max[i-1]得到的值并不一定比a[i]*min[i-1]大,因为min[i-1]可能为负,如果min[i-1]的绝对值大于max[i-1],那么a[i]*min[i-1]负负相乘的值是更大的,因此有转移方程:
max[i]=MaxinThree(a[i],a[i]*max[i-1],a[i]*min[i-1]); //求三者最大
min[i]=MininThree(a[i],a[i]*max[i-1],a[i]*min[i-1]); //求三者最小
实现代码如下:
class Test
{
static int MaxSubProduct(int[] a)
{
intn=a.Length;
int[] max=new int[n];
int[] min=new int[n];
max[0]=a[0];
min[0]=a[0];
int product=max[0];
for (int i=1;i<n;i++)
{
//求三者最大
max[i]=Math.Max(a[i]>a[i]*max[i-1]?a[i]:a[i]*max[i-1],a[i]*min[i-1]);
//求三者最小
min[i]=Math.Min(a[i]<a[i]*max[i-1]?a[i]:a[i]*max[i-1],a[i]*min[i-1]);
if(max[i]>product)
product=max[i];
}
return product;
}
public static void Main(string[] args)
{
Console.WriteLine(MaxSubProduct(new int[]{1,2,1,3,4,5,7,6}));
Console.Read();
}
}
程序的运行结果为:
5040
算法性能分析:
由于整个算法只需要对原来的数组扫描一次,因此算法的时间复杂度为O(n)。由于要借助两个临时数组,所以算法的空间复杂度为O(n)。
[考点] 如何找出数组中的乘积最大子序列
7. 把一个n×n的二维数组旋转90°。例如,给出如下数组:
[
[1,2],
[3,4]
]
旋转后的数组为:
[
[3,1],
[4,2]
]
二维数组a[n][n]顺时针旋转90°,要解决这个问题,无疑,第一件事就是找规律。
当n=1时,不需要旋转。
当n=2时,有:
a[0][0]=a[1][0]
a[1][0]=a[1][1]
a[1][1]=a[0][1]
a[0][1]=a[0][0]
在这里初步总结规律为:a[i][j]=a[n-1-j][i]
当n=3,4,5,……时也是满足的。
到这里,如果不考虑空间复杂的度的话,已经可以解决这个问题了,只需要再构建一个二维数组b[n][n],利用公式b[i][j]=a[n-1-j][i],就可以实现本题要求,实现代码如下:
public void Rotate(int[][] matrix)
{
int n=matrix.Length;
int[][]m=new int[n][];
for(int row=0;row<n;row++)
{
for(int col=0;col<n;col++)
{
m[row][col]=matrix[n-1-col][row];
}
}
//再赋值回matrix,注意形参是引用传递
for(int row=0;row<n;row++)
{
for(int col=0;col<n;col++)
{
matrix[row][col]=m[row][col];
}
}
}
为了节省空间,接着上面的分析,以n=3为例
[
[1,2,3],
[4,5,6],
[7,8,9],
]
旋转后变为
[
[7,4,1],
[8,5,2],
[9,6,3],
]
把焦点放在一个元素的旋转上,可以看出要在原数组-扣旋转,在不丢失数据的情况下,每个值的要旋转会“波及”4个数,以1为例波及了1,3,7,9,每个数旋转要不丢失数据就要考虑如何让这个4个数都得以保留。前边总结了规律a[i][j]=a[n-1-j][i],分析每组被波及的数,可以得出这里波及的4个数其实就是:
a[i][j]
a[n-1-j][i]
a[n-1-i][n-1-j]
a[n-1-(n-1-j)][n-1-i]=a[j][n-1-i]
把焦点放在一个元素上,就可以在原数组上进行交换,空间问题得到解决。
回到整个二维数组上来,每个数的旋转会波及4个数,相当于用上面的方法,每旋转一个数,就把一组的4个数都旋转了,所以现在的问题就是如何才能完整地把所有的数都旋转90°且不会多旋转,继续分析,
n=1时,不需旋转。
n=2时,只需要完成1(a[0][0])的旋转,就完成了整个数组的旋转。
n-3时,需要完成1,2(a[0][0],a[0][1])的旋转,就完成了整个数组的旋转。
n=4时,需要完成1,2,3,6(a[0][0至3],a[1][1])的旋转。
n=5时,需要完成(a[0][0至4],a[1][1至2])
综上可以总结出,对于要旋转的数a[i][j]满足,i<n/2且i<=j<n-1-i。
实现代码如下:
class Test
{
static void RotateV2(int[][] matrix)
{
int n=matrix.Length;
int limit=(n-1)/ 2;
for(int i=0; i<=limit; i++)
{
for(int j=i; j<n-1-i; j++)
{
int temp=matrix[i][j];
matrix[i][j]=matrix[n-1-j][i];
matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
matrix[j][n-1-i]=temp;
}
}
}
public static void Main(string[] args)
{
int[][]matrix=new int[][] {new int[] {1,2,3}, new int[] {4,5,6}, new int[] {7,8,9}};
RotateV2(matrix);
for (int i=0; i<matrix.Length; i++)
{
for (int j=0; j<matrix[i].Length; j++)
{
Console.Write(matrix[i][j]+" ");
}
Console.WriteLine("");
}
Console.Read();
}
}
程序的运行结果为:
7 4 1
8 5 2
9 6 3
算法性能分析:
算法使用了双重循环,因此时间复杂度为O(n2)。由于要借助固定临时变量所以空间复杂度为O(l)。
[考点] 如何对数组进行旋转
8. 给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A)-SUM(B)|最大。返回这个最大的差值。需要注意的是,子数组最少包含一个数。例如数组[1,2,-3,1],返回6。
首先求出从左到右遍历数的最大子数组maxLeft、最小子数组minLeft,然后从右到左遍历数的最大子数组maxRight、最小子数组minRight。最后求出maxLeft与minRight的最大差值,minLeft与maxRight的最大差值。即可得出最大子数组差。
实现代码如下:
class Test
{
static int MaxDiffSubArrays(int[] nums)
{
int size=nums.Length,i=0;
int sum=0, maxValue=0;
int dec=0, minValue=0;
int[] maxLeft=new int[size];
int[] minLeft=new int[size];
int[] maxRight=new int[size];
int[] minRight=new int[size];
sum=maxValue=maxLeft[0]=nums[0];
for(i= ; i<size; i++)
{
if(sum<0)
{
sum=nums[i];
}
else
{
sum+=nums[i];
}
if(sum>maxValue)
{
maxValue=sum;
}
maxLeft[i]=maxValue;
}
sum=maxValue=maxRight[size-1]=nums[size-1];
for(i=size-2; i>=0; i--)
{
if(sum<0)
{
sum=nums[i];
}
else
{
sum+=nums[i];
}
if(sum>maxValue)
{
maxValue=sum;
}
maxRight[i]=maxValue;
}
dec=minValue=minLeft[0]=nums[0];
for(i=1; i<size; i++)
{
if(dec>0)
{
dec=nums[i];
}
else
{
dec+=nums[i];
}
if(dec<minValue)
{
minValue=dec;
}
minLeft[i]=minValue;
}
dec=minValue=minRight[size-1]=nums[size-1];
for (i=size-2; i>=0; 1--)
{
if(dec>0)
{
dec=nums[i];
}
else
{
dec+=nums[i];
}
if(dec<minValue)
{
minValue=dec;
}
minRight[i]=minValue;
}
int result1=0;
int result2=0;
for(i=0; i<size-1; i++)
{
result1=(result1>maxLeft[i]-minRight[i+1])?result1:(maxLeft[i]-minRight[i+1]);
result2=(result2>maxRight[i+1]-minLeft[i])?result2:(maxRight[i+1]-minLeft[i]);
}
return(result1>result2)?result1:result2;
}
public static void Main(string[] args)
{
Console.Write(MaxDiffSubArrays(new int[] {1, 2, -3, 1}));
Console.Read();
}
}
程序的运行结果为:
6
算法性能分析:
为了便于理解做了4次循环,读者可以考虑使用2次循环来实现,由于算法需要遍历四次数组,因此算法的时间复杂度为O(n)。由于要借助两4个临时大小为n数组,因此算法的空间复杂度为O(n)。
[考点] 如何求数组的最大子数组差
9. 给定一个整数数组(下标由0到n-1,其中,n表示数组的规模,数值范围由0~10000),以及一个查询列表。对于每一个查询,将会给定一个整数,请返回该数组中小于给定整数的元素的数量。例如数组[1,2,7,8,5],查询[1,8,5],返回[0,4,2]。
本题的解法是首先将数组用快速排序进行排序,然后再用二分查找法查找即可。
实现代码如下:
class Test
{
static List<int> CountOfSmallerNumber(int[]a, int[] queries)
{
var ans=new List<int>();
for(int i=0;i<queries,Length; i++)
{
//设置初始值
ans.Add(0);
}
if (a.Length==0)
{
return ans;
}
//数组排序,调用系统函数
Array.Sort(a);
int j=0;
foreach(var item in queries)
{
int res=MyQuery(a, item);
ans[j++]=res;
}
return ans;
}
static int MyQuery(int[]a, int query)
{
int high=a.Length-1;
while (a[high]>=query&&high>0)
{
high/=2;
}
while (a[high]<query && high<a.Length-1)
{
high+=1;
}
return high;
}
public static void Main(string[] args)
{
Console.WriteLine(String.Join(",", CountOfSmallerNumber(new int[] {1,2,7,8,5},new int[]{1,8,5})));
Console.Read();
}
}
程序的运行结果为:
0,4,2
算法性能分析:
因为快速排序的时间复杂度为O(nlog2n),空间复杂度为O(l),二分查找的时间复杂度也为O(nlog2n),空间复杂度为O(l),所以本题的整体时间复杂度为0(nlog2n),空间复杂度为O(l)。
[考点] 如何统计比给定整数小的数的个数
10. 对一个数组arr就地排序(就地排序是指直接在这个数组中通过交换数字完成,而不申请新的数组),使它满足如下条件:
arr[0]<=arr[1]>=arr[2]<=arr[3]...
例如,给定数组arr=[3,5,2,1,6,4],其中一个满足条件的排序结果为[1,6,2,5,3,4]。
此题很容易想到先给数组排序,然后只要每次把第二个数和第三个数调换个位置,第四个数和第五个数调换个位置,以此类推直至数组末尾,这样就能完成题目要求了,例如本题排序后数组为[1,2,3,4,5,6],按照上面进行交换后的结果为[1,3,2,5,4,6],符合题目要求。
本题还有一种比较巧妙的解法,根据题目要求的arr[0]<=arr[1]>=arr[2]<=arr[3]...,可以总结出如下规律:
1)当i为奇数时,arr[i]>=arr[i-1]
2)当i为偶数时,arr[i]<=arr[i-1]
那么只要对每个数字,根据其奇偶性,跟其对应的条件比较,如果不符合,那么就和前面的数交换位置即可,下面给出后面一种算法实现。实现代码如下:
class Test
{
static void WiggleSort(int[] nums)
{
if (nums.Length<=1)return;
for(int i=1;i<nums.Length; ++i)
{
if((i%2==1&& nums[i]<nums[i-1])||(i%2==0&& nums[i]>nums[i-1]))
{
int temp=nums[i];
nums[i]=nums[i-1];
nums[i-1]=temp;
}
}
}
public static void Main(string[]args)
{
var array=new int[]{3,5,2,1,6,4};
WiggleSort(array);
for(int i=0;i<array.Length; i+)
{
Console.Write(array[i]+"");
}
Console.Read();
}
}
程序的运行结果为:
3 5 1 6 2 4
算法性能分析:
时间复杂度为O(n),空间复杂度为O(l)。
[考点] 如何进行摇摆排序