笔试算法题（18）：常数时间删除节点 & 找到仅出现一次的两个数字

出题：给定链表的头指针和一个节点指针,要求在O(1)的时间复杂度下删除该节点

分析：

如果需要删除的节点为A，其前序节点为A-，其后续节点为A+，所以删除A之后，需要使得A-的下一个节点就是A+，常规做法是设法得到A-的索引，需要从链表头开始遍历所以时间复杂度为O（N），但实际情况是只要保证A-的下一个节点是A+就行；
所以可将A+节点的内容直接复制到A节点，这时时间复杂度为O（1），对于最后一个节点而言需要使用O（N）的时间复杂度，所以平均复杂度为(O(1)*(n-1) + O(n))/n，所以平均复杂度为O（1）；

解题：

 struct Node {

         int v;

         Node *next;

 };

 void deleteNode(Node *head, Node *target) {

         if(target == NULL) return;

         if(target->next != NULL) {

                 Node *temp=target->next;

                 target->v=temp->v;

                 target->next=temp->next;

                 delete temp;

         } else {

                 Node *temp=head;

                 while(temp!=NULL) {

                         if(temp->next != target)

                                 temp=temp->next;

                         else {

                                 temp->next=temp->next->next;

                                 delete target;

                                 break;

                         }

                 }

         }

 }

出题：给定一个整型数组，除了两个数字只出现一次外其他数字都出现了两次，要求确定这个两个只出现一次的数字，时间复杂度为O（N），空间复杂度为O（1）；

分析：

由于任何一个数字异或它本身的结果都为0，所以从左到右依次异或整型数组，数组中出现两次的数字的异或结果为0，则最终的结果就是出现一次的两个数字的异或结果；由于这两个数字肯定不同，所以结果肯定非0，为了将这两个数字分别放到一个子数组中，选取结果中第一个出现的1（第k位），这样根据第k位是否为 1将数组元素分成两个子数组，他们分别包含了一个只出现一次的数字，然后针对每一个子数组重新进行异或运算，最终就可分别得到这两个仅出现一次的数字；
本题参考何海涛老师的解法，海涛老师威武！！非常感谢何海涛老师的无私奉献，其博客地址为：
http://zhedahht.blog.163.com/

解题：

 void findInteger(int *array, int length) {

         /**

          * 获取整个数组的异或结果

          * sum1为两个目标数字的异或结果

          * */

         int sum1=array[];

         for(int i=;i<length;i++)

                 sum1^=array[i];

         /**

          * 找到sum1中最低位出现的1

          * k表示目标位上出现的1

          * */

         int k=,i;

         for(i=;i<sizeof(int)*;i++) {

                 if(sum1 & k<<i) break;

         }

         k<<=i;

         /**

          * 使用k区分不同的子数组

          * 分别对子数组使用异或

          * */

         int int1=, int2=;

         for(int i=;i<length;i++) {

                 if(array[i]&k)

                         int1^=array[i];

                 else

                         int2^=array[i];

         }

         int1^=;int2^=;

         printf("\nthe first integer: %d",int1);

         printf("\nthe second integer: %d",int2);

 }

 int main() {

         int array[]={,,,,,-,-,};

         findInteger(array,);

         return ;

 }

巴特西

笔试算法题（18）：常数时间删除节点 & 找到仅出现一次的两个数字

最新文章

热门文章