笔试算法题(29):判断元素范围1到N的数组是否有重复数字 & 计算整数的7倍

时间:2021-04-18 01:21:03

出题:一个长度为N的数组,其中的元素取值范围是1到N,要求快速判断数组是否存在重复数字;

分析:

  • 解法1:如果N个元素的范围都是在1到N,所以如果没有重复元素,则每一个位置恰好可以对应数组中的一个元素之,通过将当前元素k交换到其本身应该在的位 置k,也就是k=array[i], array[array[i],并判断是否存在duplication或者已经就绪。时间复杂度O(N),空间复杂度O(1);
  • 解法2:由于元素取值范围确定,可以使用BitMap将数组元素映射到对应的位置,如果一个位置对应了两个元素,则有重复。时间复杂度和空间复杂度都是O(N);
  • 解法3:先排序,O(NlogN),然后比较相邻元素是否相等,O(N);

解题:

 bool HasDup(int *array, int length, int cur) {
if(cur==length) return false; if(array[cur]==cur)
/**
* 注意++cur的特性,如果是cur++则参数值是cur
* 而不是cur+1
* */
return HasDup(array, length, ++cur);
else if(array[cur]==array[array[cur])
return true;
else {
int temp;
temp=array[cur];
array[cur]=array[temp];
array[temp]=temp;
return HasDup(array,length,cur);
}
}
int main() {
int array[]={,,,,,,};
if(HasDup(array,,))
printf("\nthere is duplication");
else
printf("\nthere is no duplication");
return ;
}

出题:快速计算一个整数的7倍;

分析:乘法相对较慢,所以需要转换成移位操作和加减法操作:int temp=X; X<<3 - temp

解题:

 /**
* 小于等于0,直接返回false
* 如果为2的次幂,则二进制表示中
* 有且仅有一位是1,当这个数减去1
* 则原有的1变成0,其右边的所有bit
* 变成1,此时他们的&操作为0
* */
bool If2Power(int n) {
if(n<=) return false;
/**
* 注意&的优先级小于=,所以必须加括号
* */
if((n&(n-))==) return true;
else return false;
}
/**
* 实现乘法可以转换成移位操作,向左移动移K位
* 等于*(2^K),最后再加上或者减去差值
* 注意加括号
* */
int Times7(int n) {
int t=n;
return (n<<)-t;
} int main() {
if(If2Power())
printf("\nyes");
else
printf("\nno"); printf("\n21*7= %d",Times7());
return ;
}