Home Tags Posts tagged with "双指针"

双指针

给你一个非递减的 有序 整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例:
输入:arr = [1,2,2,6,6,6,6,7,10]
输出:6
解题思路:注意该数组为有序数组,且只有一个符合要求的整数;
方法一:双指针法
  1. 数组有序,且某元素出现次数超过25%
  2. 那么对于此元素第1次出现位置,加25%数组长度,必定仍为它自身

int findSpecialInteger(int* arr, int arrSize) {

    for (int *p = arr, *q = arr + arrSize / 4; ; p++, q++)//有序,若出现次数超过25%,则arr[i]=arr[i+arrSize/4];
        if (*p == *q) return *p;
    return 0;  
}
方法二:遍历
int findSpecialInteger(int* arr, int arrSize){
//int len = arrSize/4;
int i = 1,cou = 0;
int temp = arr[0];
    while(i < arrSize){
if(temp == arr[i]){
cou++;
            if(cou*4 >= arrSize){
                break;
            }
        }
        else{
            cou = 0;
        }
        temp = arr[i];
        i++;//在一次循环中进行移动;
    }
    return temp;
}
方法三:二分查找
对于此题来说二分查找无意义,故不讨论;

实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
注意:本题相对原题稍作改动
示例:
输入: 1->2->3->4->5 和 k = 2
输出: 4
解题思路:双指针,同起点出发,A先走K步,之后B再跟A一起出发,当A指向空时,B指向目标值,循环结束;
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k){
                struct ListNode*a=head;
                while(k–)
                {
                       a=a->next;
                }//结束后a指向3;
                while(a)
               { 
                     a=a->next;
                     head=head->next;
                }
return head->val;
}