欢迎光临
我的个人博客网站

算法面试题二:旋转数组,存在重复元素,只出现一次的数字

这里介绍排序算法及贪心算法的个人解决方法

算法面试题二:旋转数组,存在重复元素,只出现一次的数字

题目一:旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入:nums = [-1,-100,3,99], k = 2 输出:[3,99,-1,-100] 解释:  向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]

提示:

1 <= nums.length <= 2 * 104 -231 <= nums[i] <= 231 - 1 0 <= k <= 105

答案:

/**  * @param {number[]} nums  * @param {number} k  * @return {void} Do not return anything, modify nums in-place instead.  */ var rotate = function(nums, k) {     if(nums.length == 1 || k == 0){         return nums     }     if(k > nums.length){         k = k%nums.length     }     k = nums.length - k;     for(let ii=0;ii<k;ii++){         nums.push("0");     }     let value;     let length = nums.length;     for(let i=0;i<nums.length;i++){         value = nums[i];         if(i < k){             nums[i] = nums[length - k + i];             nums[length - k + i] = value;         }else{              nums[i] = nums[i-k];              nums[i-k] = value;         }      }     nums.splice(length-k,k);     return nums; };

题目二:存在重复元素

给定一个整数数组,判断是否存在重复元素。  如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false 。

示例 1:

输入: [1,2,3,1] 输出: true

示例 2:

输入: [1,2,3,4] 输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2] 输出: true

答案一:

/**  * @param {number[]} nums  * @return {boolean}  */ var containsDuplicate = function(nums) {     let bind = false;     var arr = nums.sort();     for(let i=0;i<arr.length-1;i++){         if(arr[i] == arr[i+1]){             bind = true;         }     }     return bind; };

答案二:

/**  * @param {number[]} nums  * @return {boolean}  */ var containsDuplicate = function(nums) {     let bind = false;     for(let i=0;i<nums.length;i++){         for(let j=0;j<nums.length;j++){           if(nums[i] == nums[j] && i == j){             bind = true           }         }     }     return bind; };

题目三:只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1] 输出: 1

示例 2:

输入: [4,1,2,1,2] 输出: 4

答案一:

/**  * @param {number[]} nums  * @return {number}  */ var singleNumber = function(nums) {     nums = nums.sort();     if(nums.length == 1){         return nums[0];     }     let value = null;     for(let i=0;i<nums.length-1;i++){        if(nums[i] == nums[i+1]){            i++;        }else{            value = nums[i];        }     }     if(value == null) value = nums[nums.length-1]     return value; };

答案二:

var singleNumber = function(nums) {     let value;     for(let i=0;i<nums.length;i++){         let arr = 0;         for(let j=0;j<nums.length;j++){             if(nums[i] == nums[j]){                 arr++;             }         }         if(arr%2 == 1){             value = nums[i];         }     }     return value; };

如果对你有帮助,请你点个推荐,我会和你一起进步,加油(*^▽^*)。

赞(0) 打赏
未经允许不得转载:张拓的天空 » 算法面试题二:旋转数组,存在重复元素,只出现一次的数字
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏