169.?多數(shù)元素

難度：簡(jiǎn)單

給定一個(gè)大小為?n?的數(shù)組?nums?，返回其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)?大于?? n/2 ??的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例?1：

輸入：nums = [3,2,3]
輸出：3

示例?2：

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

進(jìn)階：嘗試設(shè)計(jì)時(shí)間復(fù)雜度為 O(n)、空間復(fù)雜度為 O(1) 的算法解決此問題。?

思路：采用兩兩相消的方法，因?yàn)槎鄶?shù)元素出現(xiàn)的次數(shù)是大于n/2的，所以只要兩兩不相等的元素相消，剩下的那個(gè)元素就肯定是多數(shù)元素了

代碼：

class Solution {public int majorityElement(int[] nums) {int more = nums[0];int count = 1;for(int i = 1; i < nums.length;i++ ){if(more == nums[i]) {count++;}else if(count == 0) {more = nums[i];count++;}else {count--;}}return more;}
}

運(yùn)行結(jié)果：

?

189.?輪轉(zhuǎn)數(shù)組

難度：中等

相關(guān)企業(yè)

給定一個(gè)整數(shù)數(shù)組?nums，將數(shù)組中的元素向右輪轉(zhuǎn)?k?個(gè)位置，其中?k?是非負(fù)數(shù)。

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

示例?2:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋: 
向右輪轉(zhuǎn) 1 步: [99,-1,-100,3]
向右輪轉(zhuǎn) 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

進(jìn)階：

• 盡可能想出更多的解決方案，至少有?三種?不同的方法可以解決這個(gè)問題。
• 你可以使用空間復(fù)雜度為?O(1)?的?原地?算法解決這個(gè)問題嗎？

?思路：翻轉(zhuǎn)三次，如圖所示

?代碼：

class Solution {public void reverse(int[] nums,int left,int right){       while(left < right){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}}public void rotate(int[] nums, int k) {int length = nums.length;k%=length;reverse(nums,0,length-1);reverse(nums,0,k-1);reverse(nums,k,length-1);}
}

運(yùn)行結(jié)果：

?