题解 | #有序数组中出现一次的元素#

有序数组中出现一次的元素

https://www.nowcoder.com/practice/4c67fc80c37649ac906fee76ec82beb4

import java.util.*;

/**
 * NC377 有序数组中出现一次的元素
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param v int整型一维数组
     * @return int整型
     */
    public int singleElement (ArrayList<Integer> v) {
//        return solution1(v);
        return solution11(v);
//        return solution2(v);
//        return solution3(v);
//        return solution4(v);
//        return solution5(v);
    }

    /**
     * 二分
     * @param v
     * @return
     */
    private int solution1(ArrayList<Integer> v){
        int n = v.size();

        int result = -1;

        int left = 0;
        int right = n-1;
        int mid;
        int pre,after;
        while(left <= right){
            mid = left+(right-left)/2;
            if(mid%2 == 1){
                pre = mid-1;
                after = mid+1;
                if(0<=pre && v.get(pre).equals(v.get(mid))){
                    left = mid+1;
                    continue;
                }
                if(after<n && v.get(mid).equals(v.get(after))){
                    right = mid-1;
                    continue;
                }
            }
            // 最终结果一定是在 偶数索引位置
            else{
                pre = mid-1;
                after = mid+1;
//                if(0<=pre && v.get(pre).equals(v.get(mid))){
//                    right = mid-1;
//                    continue;
//                }
//                if(after<n && v.get(mid).equals(v.get(after))){
//                    left = mid+1;
//                    continue;
//                }
                // 可减2
                if(0<=pre && v.get(pre).equals(v.get(mid))){
                    right = mid-2;
                    continue;
                }
                // 可加2
                if(after<n && v.get(mid).equals(v.get(after))){
                    left = mid+2;
                    continue;
                }
                // 前后 都不相同
                result = v.get(mid);
                break;
            }
        }

        return result;
    }

    /**
     * 二分
     * @param v
     * @return
     */
    private int solution11(ArrayList<Integer> v){
        int n = v.size();

        int result = -1;

        int left = 0;
        int right = n-1;
        int mid;
        int pre,after;
        while(left <= right){
            mid = left+(right-left)/2;
            if(mid%2 == 1){
                pre = mid-1;
                after = mid+1;
                if(0<=pre && v.get(pre).equals(v.get(mid))){
                    left = mid+1;
                }else if(after<n && v.get(mid).equals(v.get(after))){
                    right = mid-1;
                }
            }else{
                pre = mid-1;
                after = mid+1;
                if(0<=pre && v.get(pre).equals(v.get(mid))){
                    right = mid-2;
                }else if(after<n && v.get(mid).equals(v.get(after))){
                    left = mid+2;
                }else{
                    result = v.get(mid);
                    break;
                }
            }
        }

        return result;
    }

    /**
     * 二分: 简化
     * @param v
     * @return
     */
    private int solution2(ArrayList<Integer> v){
        int n = v.size();

        int left = 0;
        int right = n-1;
        int mid;
        int pre,after;
        while(left < right){
            mid = left+(right-left)/2;
            if(mid%2 == 1){
                pre = mid-1;
                if(0<=pre && v.get(pre).equals(v.get(mid))){
                    left = mid+1;
                }else{
                    right = mid;
                }
            }else{
                after = mid+1;
                if(after<n && v.get(mid).equals(v.get(after))){
//                    left = mid+1;
                    // 可加2
                    left = mid+2;
                }else{
                    right = mid;
                }
            }
        }

        return v.get(left);
    }

    /**
     * 二分: 再简化
     * @param v
     * @return
     */
    private int solution3(ArrayList<Integer> v){
        int n = v.size();

        int left = 0;
        int right = n-1;
        int mid;
        while(left < right){
            mid = left+(right-left)/2;

            if(v.get(mid).equals(v.get(mid^1))){
                left = mid+1;
            }else{
                right = mid;
            }
        }

        return v.get(left);
    }

    /**
     * 二进制: 位运算(异或^)
     * @param v
     * @return
     */
    private int solution4(ArrayList<Integer> v){
        int result = 0;
        for(int num: v){
            result ^= num;
        }

        return result;
    }

    /**
     * 遍历
     * @param v
     * @return
     */
    private int solution5(ArrayList<Integer> v){
        int n = v.size();

        int result = 0;

        for(int i=0; i<n; i+=2){
            if((i==n-1) || (!v.get(i).equals(v.get(i+1)))){
                result = v.get(i);
                break;
            }
        }

        return result;
    }
}

全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务