面试题3 数组中的重复数字中不修改原数据的版本有误,比如给定01134567就无法得出重复数字1,因为这里做二分的时候具有不确定性,也就是count跟end-start+1之间并不是必然联系的。改进版本查找任意一个重复数字的时间复杂度在O(nlogn)到O(nn)之间
// 不修改原数据的改进版本// 只找一个重复的数据时,时间复杂度在O(nlogn)到O(nn)之间// 找所有重复就是O(nn)bool getDupNum3(int* pData, int length){if (pData == NULL || length <= 1){return false;}int start = 0;int end = length - 1;return innerGetDupNumber(pData, length, start, end);}
bool innerGetDupNumber(int* pData, int length, int start, int end){int count = countRange(pData, length, start, end);if (start == end){if (count > 1){printf(“duplicate number %d\n”, start);return true;}return false;}
int mid = start + ((end - start) >> 1);if (innerGetDupNumber(pData, length, start, mid)){return true;}return innerGetDupNumber(pData, length, mid + 1, end);}
面试题47,礼物的最大价值,中间有一行“每次向左或者向下移动一格”应该改为“每次向右或者向下移动一格”。
书中的源代码在哪里下载
面试题3 数组中的重复数字中不修改原数据的版本有误,比如给定01134567
就无法得出重复数字1,因为这里做二分的时候具有不确定性,也就是count跟end-start+1之间并不是必然联系的。改进版本查找任意一个重复数字的时间复杂度在O(nlogn)到O(nn)之间
// 不修改原数据的改进版本
// 只找一个重复的数据时,时间复杂度在O(nlogn)到O(nn)之间
// 找所有重复就是O(nn)
bool getDupNum3(int* pData, int length)
{
if (pData == NULL || length <= 1)
{
return false;
}
int start = 0;
int end = length - 1;
return innerGetDupNumber(pData, length, start, end);
}
bool innerGetDupNumber(int* pData, int length, int start, int end)
{
int count = countRange(pData, length, start, end);
if (start == end)
{
if (count > 1)
{
printf(“duplicate number %d\n”, start);
return true;
}
return false;
}
int mid = start + ((end - start) >> 1);
if (innerGetDupNumber(pData, length, start, mid))
{
return true;
}
return innerGetDupNumber(pData, length, mid + 1, end);
}
面试题47,礼物的最大价值,中间有一行“每次向左或者向下移动一格”应该改为“每次向右或者向下移动一格”。
书中的源代码在哪里下载
书中的源代码在哪里下载
书中的源代码在哪里下载