难度系数排序，容易题1-10题：
Cosine Similarity new
Fizz Buzz
O(1)检测2的幂次
x的平方根
不同的路径
不同的路径 II
两个字符串是变位词
两个链表的和
中位数
主元素
Cosine Similarity
题目：
Cosine similarity is a measure of similarity between two vectors of an inner product space that measures the cosine of the angle between them. The cosine of 0° is 1, and it is less than 1 for any other angle.
See wiki: Cosine Similarity
Here is the formula:
Given two vectors A and B with the same size, calculate the cosine similarity.
Return 2.0000 if cosine similarity is invalid (for example A = [0] and B = [0]).
样例
Given A = [1, 2, 3], B = [2, 3 ,4].
Return 0.9926.
Given A = [0], B = [0].
Return 2.0000
解题：
Java程序：
class Solution {
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: Cosine similarity.
*/
public double cosineSimilarity(int[] A, int[] B) {
// write your code here
int ab = 0;
double aa = 0.0;
double bb = 0.0;
if(A.length != B.length) return 2.0000;
if(A.length==1 && A[0]==0 || B.length==1 && B[0]==0)
return 2.0000;
for(int i=0;i<A.length;i++){
ab += A[i] * B[i];
aa += A[i] * A[i];
bb += B[i] * B[i];
}
if(aa==0 || bb==0) return 2.0000;
aa = Math.sqrt(aa);
bb = Math.sqrt(bb);
return ab/(aa*bb);
}
}
Python程序：
class Solution:
"""
@param A: An integer array.
@param B: An integer array.
@return: Cosine similarity.
"""
def cosineSimilarity(self, A, B):
# write your code here
ab = 0
aa = 0
bb = 0
if(len(A)!=len(B)) : return 2.0000
# if len(A)==1 and A[0] = 0 or len(B)==1 and B[0]=0 : return 2.0000;
for i in range(len(A)):
ab += A[i]*B[i]
aa += A[i]*A[i]
bb += B[i]*B[i]
if aa==0 or bb==0 : return 2.0000
aa = aa**0.5
bb = bb**0.5
return ab/(aa*bb)
Fizz Buzz
题目：
给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：
- 如果这个数被3整除，打印
fizz. - 如果这个数被5整除，打印
buzz. - 如果这个数能同时被
3和5整除，打印fizz buzz.
样例
比如 n = 15, 返回一个字符串数组：
["1", "2", "fizz", "4", "buzz", "fizz", "7", "8", "fizz", "buzz", "11", "fizz", "13", "14", "fizz buzz"]
解题：
Java程序:
class Solution {
/**
* param n: As description.
* return: A list of strings.
*/
public ArrayList<String> fizzBuzz(int n) {
ArrayList<String> results = new ArrayList<String>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) {
results.add("fizz buzz");
} else if (i % 5 == 0) {
results.add("buzz");
} else if (i % 3 == 0) {
results.add("fizz");
} else {
results.add(String.valueOf(i));
}
}
return results;
}
}
Python程序：
class Solution:
"""
@param n: An integer as description
@return: A list of strings.
For example, if n = 7, your code should return
["1", "2", "fizz", "4", "buzz", "fizz", "7"]
"""
def fizzBuzz(self, n):
results = []
for i in range(1, n+1):
if i % 15 == 0:
results.append("fizz buzz")
elif i % 5 == 0:
results.append("buzz")
elif i % 3 == 0:
results.append("fizz")
else:
results.append(str(i))
return results
O(1)检测2的幂次
O(1) Check Power of 2
题目：
用 O(1) 时间检测整数 n 是否是 2 的幂次。
样例
n=4，返回 true;
n=5，返回 false.
注意
O(1) 时间复杂度
解题：
Java程序：
class Solution {
/*
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
// write your code here
if(n==1) return true;
if(n<=0 || n%2==1) return false;
while(n!=0){
n=n/2;
if(n==1) return true;
if(n%2==1) return false;
}
return true;
}
};
原来就是利用到奇数不是2的次幂，进行排除
这里的时间复杂度应该是O(log2n) ，在最坏的情况下n就是2的幂次方，while循环要进行到k次，2^k = n
但是这个也AC了
看到下面程序，利用到若n是2的次幂则，n和n-1的二进制表示对应位置都不一样
class Solution {
/*
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
// write your code here
if(n<=0) return false;
return (n & (n-1)) == 0 ? true : false;
}
};
Python程序：
class Solution:
"""
@param n: An integer
@return: True or false
"""
def checkPowerOf2(self, n):
# write your code here
if n<=0 : return False
if n==1 : return True
if n%2==1 : return False
while n!=0:
n/=2
if n==1 or n==0: return True
if n%2==1:return False
return True
x的平方根
Sqrt(x)
题目：
实现 int sqrt(int x) 函数，计算并返回 x 的平方根。
样例
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
挑战
O(log(x))
解题：
Java程序：
这样也行！！！
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
return (int)Math.sqrt(x);
}
}
下面程序通过45%
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
// return (int)Math.sqrt(x);
int n = x/2 + 1;
int min = n;
int res = 0;
for(int i=1;i<=n;++i){
int tmp = x - i*i;
if(tmp >=0 && tmp<=min){
min = tmp;
res = i;
}
}
return res;
}
}
官方答案，利用二分法，寻找离sqrt(x)最近的数
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
// return (int)Math.sqrt(x);
int left = 1;
int right = x/2 + 1;
int mid;
int res=1;
int tmp;
if (x<2) return x;
while(left<=right){
mid = left + (right - left)/2;
tmp = x/mid;
if(tmp>mid){
left = mid + 1;
res = mid;
}else if(tmp<mid){
right = mid - 1;
}else
return mid;
}
return res;
}
}
时间复杂度O(log2x)
Python程序：
class Solution:
"""
@param x: An integer
@return: The sqrt of x
"""
def sqrt(self, x):
# write your code here
if x<2 : return x
left = 1
right = x/2 + 1
res = 0
mid = 0
while left <= right:
mid = left + (right - left)/2
tmp = x/mid
if tmp>mid:
left = mid + 1
res = mid
elif tmp<mid:
right = mid - 1
else:
return mid;
return res
不同的路径
Unique Paths
题目：
有一个机器人的位于一个M×N个网格左上角（下图中标记为'Start'）。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角（下图中标记为'Finish'）。
问有多少条不同的路径？
样例
| 1,1 | 1,2 | 1,3 | 1,4 | 1,5 | 1,6 | 1,7 |
| 2,1 | ||||||
| 3,1 | 3,7 |
以上3 x 7的网格中，有多少条不同的路径？
注意
n和m均不超过100
解题：
直接数学分析，需要向下走m-1步，在向右走n-1步，共m+n-2步，在这m+n-2步中有m-1步是向下走的，同时向下走的方式确定了，向右走的步也确定了，共有Cm+n-2m-1 种
我们求的是到右下角的路径有多少个，设A[m-1][n-1]就是到该点的路径和，则其路径和等于到临近右侧m-1，n-2的路径和A[m-1][n-2] + 临近上侧m-2,n-1的路径和A[m-2][n-1],
写成通项的形式：A[i][j] = A[i][j-1] + A[i-1][j]
对于初始化：A[i][0] = 1 A[0][j] = 1 ,这里利用到的是杨辉三角的思想
Java程序：
public class Solution {
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
public int uniquePaths(int m, int n) {
// write your code here
int arr[][] = new int[m][n];
for(int i=0;i<m;i++)
arr[i][0] = 1;
for(int i=0;i<n;i++)
arr[0][i] = 1;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++)
arr[i][j] = arr[i][j-1] + arr[i-1][j];
}
return arr[m-1][n-1];
}
}
Python代码：
class Solution:
"""
@param n and m: positive integer(1 <= n , m <= 100)
@return an integer
"""
def uniquePaths(self, m, n):
# write your code here
A = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
A[i][0] = 1
for j in range(n):
A[0][j] = 1
for i in range(1,m):
for j in range(1,n):
A[i][j] = A[i][j-1] + A[i-1][j]
return A[m-1][n-1]
官方给的方法：利用深度优先的方法，时间复杂度O(n4)空间复杂度(n)
Java程序：
public class Solution {
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
public int uniquePaths(int m, int n) {
// write your code here
if(m<0||n<0) return 0;
if(m==1 && n==1) return 1;
return uniquePaths(m-1,n) + uniquePaths(m,n-1);
}
}
运行到27%的测试程序，运行超时
官方解题报告中又讲到利用深度搜索+缓存的方法 叫备忘录法
这里说的时间复杂度是O(n2)空间复杂O(n2) 不是很理解，同时程序只是对非零项进行计算，竟然可以通过测试
Java程序：
public class Solution {
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
public int uniquePaths(int m, int n) {
// write your code here
//00 未用到
int[][] f= new int[m+1][n+1];
return dfs(f,m,n);
}
private int dfs(int[][] f,int m,int n){
if(m<1 || n<1) return 0;
if(m==1 && n==1) return 1;
return getOrUpdate(f,m-1,n) + getOrUpdate(f,m,n-1);
}
private int getOrUpdate(int[][] f,int m,int n){
if(f[m][n]>0) return f[m][n];
else {
f[m][n] = dfs(f,m,n);
return f[m][n];
}
}
}
Python程序：
class Solution:
"""
@param n and m: positive integer(1 <= n , m <= 100)
@return an integer
"""
def uniquePaths(self, m, n):
# write your code here
f = [[0 for _ in range(n+1)] for _ in range(m+1)]
return self.dfs(f,m,n)
def dfs(self,f,m,n):
if m<1 or n<1 : return 0
if m==1 and n==1 : return 1
return self.getOrUpdate(f,m-1,n) + self.getOrUpdate(f,m,n-1)
def getOrUpdate(self,f,m,n):
if f[m][n]>0 :
return f[m][n]
else:
f[m][n] = self.dfs(f,m,n)
return f[m][n]
在上面的深度优先算法中，有重复计算
而通过getOrUpdate方法，只对f[m][n]==0的情况进行在找路径
不同的路径 II
Unique Paths 2
题目：
跟进“不同的路径”：
现在考虑网格中有障碍物，那样将会有多少条不同的路径？
网格中的障碍和空位置分别用和来表示。
样例
如下所示在3x3的网格中有一个障碍物：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
一共有2条不同的路径从左上角到右下角。
注意
m和n均不超过100
解题：
Java程序：
public class Solution {
/**
* @param obstacleGrid: A list of lists of integers
* @return: An integer
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// write your code here
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) return 0;
int A[][] = new int[m][n];
A[0][0] = obstacleGrid[0][0]==1?0:1;
for(int i=1;i<m;i++)
A[i][0] = obstacleGrid[i][0]==1?0:A[i-1][0];
for(int j=1;j<n;j++)
A[0][j] =obstacleGrid[0][j]==1?0:A[0][j-1];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
A[i][j] = obstacleGrid[i][j]==1?0:A[i][j-1]+ A[i-1][j];
return A[m-1][n-1];
}
}
Python程序：
class Solution:
"""
@param obstacleGrid: An list of lists of integers
@return: An integer
"""
def uniquePathsWithObstacles(self, obstacleGrid):
# write your code here m ,n= len(obstacleGrid),len(obstacleGrid[0])
if obstacleGrid[0][0]==1 or obstacleGrid[m-1][n-1]==1 : return 0
A = [[0 for _ in range(n)] for _ in range(m)]
A[0][0] = 0 if obstacleGrid[0][0]==1 else 1
for i in range(1,m):
A[i][0] = 0 if obstacleGrid[i][0]==1 else A[i-1][0]
for j in range(1,n):
A[0][j] = 0 if obstacleGrid[0][j]==1 else A[0][j-1]
for i in range(1,m):
for j in range(1,n):
A[i][j] = 0 if obstacleGrid[i][j]==1 else A[i-1][j]+A[i][j-1]
return A[m-1][n-1]
这个是在上面程序的基础上进行修改，对于边界点，先找到通路，自己所在的位置可达，就依赖于上一点是否是通路
对于中间点也是，自己所在的位置可达，就依赖于其临近左侧和上侧点的情况了
两个字符串是变位词
Two Strings Are Anagrams
题目：
写出一个函数 anagram(s, t) 去判断两个字符串是否是颠倒字母顺序构成的
样例
给出 s="abcd"，t="dcab"，返回 true
Challenge
O(n) time, O(1) extra space
解题：
定义一个HashMap,key=字符串中的每个字符，value=字符出现的次数，第一个字符串s每个入HashMap，并更改value的值，第二个字符串t，当key不存在时候或者value《0时候，返回false。
Java程序：
public class Solution {
/**
* @param s: The first string
* @param b: The second string
* @return true or false
*/
public boolean anagram(String s, String t) {
// write your code here
if(s.length()!=t.length())
return false;
int len = s.length();
HashMap map = new HashMap();
for(int i=0;i<len;i++){
char ch = s.charAt(i);
if(map.containsKey(ch)==false){
map.put(ch,1);// key value
}else{
int tmpvalue = (Integer) map.get(ch) + 1;
map.put(ch,tmpvalue);
}
}
for(int i=0;i<len;i++){
char ch = t.charAt(i);
if(map.containsKey(ch)==false){
return false;
}else{
int tmpvalue = (Integer) map.get(ch) - 1;
map.put(ch,tmpvalue);
if((Integer) map.get(ch)<0)
return false;
}
}
return true;
}
};
这里时间复杂度是O(n)，空间复杂度也是O(n)
网上看到下面的方法，256个字符，定义一个长度是256的数组，存放每个字符出现的次数
Java程序：
public class Solution {
/**
* @param s: The first string
* @param b: The second string
* @return true or false
*/
public boolean anagram(String s, String t) {
// write your code here
if(s.length()!=t.length())
return false;
int len = s.length();
int A[] = new int[256];
// int tA[] = new int[256];
for(int i=0;i<len;i++)
A[s.charAt(i)]++;
for(int i=0;i<len;i++)
A[t.charAt(i)]--;
for(int i=0;i<256;i++)
if(A[i]!=0)
return false;
return true;
}
}
Python程序：
class Solution:
"""
@param s: The first string
@param b: The second string
@return true or false
"""
def anagram(self, s, t):
# write your code here
if len(s) != len(t):
return False
dict={} for si in s:
if dict.has_key(si)==False:
dict[si] = 1
else:
dict[si] = dict.get(si) + 1
for ti in t:
if dict.has_key(ti)==False:
return False
else:
dict[ti] = dict.get(ti) - 1
if dict[ti] < 0:
return False
return True
利用到python的字典和HashMap差不多的
两个链表的和
Add Two Numbers
题目：
你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
样例
给出两个链表 3->1->5->null 和 5->9->2->null，返回 8->0->8->null
解题：
链表求和，判断是否进位，链表是否结束，和之前leetcode上的题目一样，由于节点搞错了，搞了好久的
Java程序：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/ public ListNode addLists(ListNode l1, ListNode l2) {
// write your code here ListNode head= new ListNode(0);
ListNode current = head;
int quotients=0;
while(l1!=null && l2!=null){
int sum = quotients + l1.val + l2.val;
quotients = sum/10;
// l1.val = sum%10;
current.next = new ListNode(sum%10);
current = current.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1!=null){
int sum = quotients + l1.val;
quotients = sum/10;
current.next = new ListNode(sum%10);
current = current.next;
l1 = l1.next;
} while(l2!=null){
int sum = quotients + l2.val;
quotients = sum/10;
current.next = new ListNode(sum%10);
current = current.next;
l2 = l2.next;
}
if(quotients==1){
current.next = new ListNode(1);
current = current.next; }
return head.next;
}
}
Python程序：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
# @param l1: the first list
# @param l2: the second list
# @return: the sum list of l1 and l2
def addLists(self, l1, l2):
# write your code here
head = ListNode(0)
current = head;
sum = 0
while l1!=None or l2!=None:
if l1!=None:
sum+=l1.val
l1=l1.next
if l2!=None:
sum+=l2.val
l2=l2.next
current.next = ListNode(sum%10)
current = current.next
sum/=10
if sum==1:
current.next = ListNode(1)
current = current.next
return head.next
中位数
Median
题目：
给定一个未排序的整数数组，找到其中位数。
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
样例
给出数组[4, 5, 1, 2, 3]， 返回 3
给出数组[7, 9, 4, 5]，返回 5
挑战
时间复杂度为O(n)
解题：
利用冒泡排序，一次排序介绍后能够回到最后的位置，若是升序排序，每次都要数回到较大的位置，第一次，最大元素到位，第二次，次大元素到位，...,
第len/2-1(奇数长度时候是len/2)次回到自己的位置，也就是中位数的位置，但是这里的时间复杂度是O(n2)
由于存在只有一个元素的情况，不满足冒泡排序，直接返回第0个元素。
Java程序：
public class Solution {
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public int median(int[] nums) {
// write your code here
int left = 0;
int len = nums.length;
if(len%2==1)
return BubbleSort(nums,len/2,len);
else
return BubbleSort(nums,len/2-1,len);
}
int BubbleSort(int[] nums,int mid,int len){
int i,j,flag;
int tmp;
for(i=len-1;i>=1;i--){
flag = 0;
for(j=1;j<=i;++j)
if(nums[j-1]>nums[j]){
tmp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = tmp;
flag = 1;
}
if(i==mid)
return nums[i];
}
return nums[0];
}
}
总耗时: 3139 ms
下面是利用到快速排序的思想，每次找到第k大的数，同时又划分数据集，一个比他大，一个比他小的，再选取合适的范围进行调整，这里开始自己写，测试程序运行到32%处报错，一直修改不好，下面是参考网上程序修改如下：
public class Solution {
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public int median(int[] nums) {
// write your code here
int left = 0;
int len = nums.length;
if(len%2==1)
return findKth(nums,len/2,0,len-1);
else
return findKth(nums,len/2-1,0,len-1);
}
public int findKth(int[]nums, int mid,int left,int right){
if(mid==left && left ==right)
return nums[mid];
if(left>=right)
return -1;
int pivot;
int i=left,j=right;
pivot = nums[left];
while(i!=j){
while(j>i && nums[j]>=pivot) --j;
nums[i] = nums[j];
while(i<j&&nums[i]<=pivot) ++i;
nums[j] = nums[i];
}
nums[i] = pivot;
if(i==mid)
return nums[i];
else if(i>mid)
return partitions(nums, mid, left, i-1);
else
return partitions(nums, mid, i+1, right);
}
}
总耗时: 2358 ms
我记忆中的快速排序是这样的，开始我搞错的原因就是结束条件搞错了
public class Solution {
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public int median(int[] nums) {
// write your code here
int left = 0;
int len = nums.length;
if(len%2==1)
return fintKth(nums,len/2,0,len-1);
else
return fintKth(nums,len/2-1,0,len-1);
}
public int fintKth(int[]nums, int mid,int left,int right){
if(mid==left && left ==right)
return nums[mid];
if(left>=right)
return -1;
int i=left;
int j=right;
int pivot = nums[left];
while(i!=j){
while(j>i && nums[j]>pivot) --j;
if(i<j){
nums[i] = nums[j];
++i;
}
while(i<j&&nums[i]<pivot) ++i;
if(i<j){
nums[j] = nums[i];
--j;
}
}
nums[i] = pivot;
if(i==mid)
return nums[i];
else if(i>mid )
return partitions(nums, mid, left, i-1);
else
return partitions(nums, mid, i+1, right);
}
}
总耗时: 2997 ms
Python程序：
class Solution:
"""
@param nums: A list of integers.
@return: An integer denotes the middle number of the array.
"""
def median(self, nums):
# write your code here
left = 0
right = len(nums)
mid = right/2
if right%2==1:
return self.findKth(nums,mid,left,right-1)
elif right%2==0:
return self.findKth(nums,mid-1,left,right-1) def findKth(self,nums,mid,left,right):
if left==mid and mid == right:
return nums[mid]
if left>right:
return -1
i = left
j = right
pivot = nums[left]
while(i<j):
while(i<j and nums[j]>=pivot):
j-=1
if i<j:
nums[i] = nums[j]
while(i<j and nums[i]<=pivot):
i+=1
if i<j:
nums[j] = nums[i]
nums[i] = pivot
if i == mid:
return nums[mid]
elif i>mid:
return self.findKth(nums,mid,left,(i-1))
elif i<mid:
return self.findKth(nums,mid,(i+1),right)
总耗时: 475 ms
主元素
Majority Number
题目：
给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。
样例
给出数组[1,1,1,1,2,2,2]，返回 1
挑战
要求时间复杂度为O(n)，空间复杂度为O(1)
解题：
利用HashMap，key=这个数，value=这个数出现的次数，当发现出现次数大于len/2的时候结束，返回这个数就是majority number，但是这里的时间复杂度和空间复杂度都是O(n)
Java程序：
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
int numsLen = nums.size();
HashMap hmap = new HashMap();
int majority = 0;
for(int i = 0;i<numsLen;i++){
int num = nums.get(i);
if(hmap.containsKey(num)==false){
hmap.put(num,1);
}else{
hmap.put(num,(Integer)hmap.get(num)+1);
if((Integer)hmap.get(num)>numsLen/2){
majority= num;
break;
}
}
}
return majority;
}
}
总耗时: 2294 ms
上面程序有点缺陷，只在第二次出现的时候才返回majority number，定义的初始majority = 0，测试数据中有一个只有一个0长度也是1，造成无法测出错误
修改后：
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
int numsLen = nums.size();
HashMap hmap = new HashMap();
int majority = 0;
for(int i = 0;i<numsLen;i++){
int num = nums.get(i);
if(hmap.containsKey(num)==false)
hmap.put(num,1);
else
hmap.put(num,(Integer)hmap.get(num)+1);
if((Integer)hmap.get(num)>numsLen/2){
majority= num;
break;
}
}
return majority;
}
}
总耗时: 2152 ms
Python程序：
class Solution:
"""
@param nums: A list of integers
@return: The majority number
"""
def majorityNumber(self, nums):
# write your code here
numsLen = len(nums)
d={}
for num in nums:
if num not in d:
d[num] = 1
else:
d[num] +=1
if d[num]>numsLen/2:
return num
总耗时: 549 ms
网上看到，利用快速排序的思想，中位数一定是主元素，这里和上一题有很对应了。直接利用上面的找中位数的程序
Java程序：
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
int numsLen = nums.size();
int mid = numsLen/2;
int left = 0;
int right = numsLen - 1;
return findKth(nums,mid,left,right);
}
int findKth(ArrayList<Integer> nums,int mid,int left,int right){
if(mid==left && mid == right)
return nums.get(mid);
if(left>=right)
return -1;
int i=left;
int j=right;
int pivot=nums.get(left);
while(i<j){
while(i<j && nums.get(j)>pivot) j--;
if(i<j){
nums.set(i,nums.get(j));
i++;
}
while(i<j && nums.get(i)<pivot) i++;
if(i<j){
nums.set(j,nums.get(i));
j--;
}
}
nums.set(i,pivot);
if(i==mid)
return nums.get(mid);
else if(i>mid)
return findKth(nums,mid,left,i-1);
else
return findKth(nums,mid,i+1,right);
}
}
总耗时: 2193 ms
这里的时间复杂度我一直感觉是快速排序的时间复杂度O(nlogn)，为什么都说是O(n)？不明白。。。空间复杂度道是O(1)
网上看到这样一种思想，同时删除不相同的两个元素，最后剩余的元素一定是主元素，题目已经限制了主元素个数大于len/2,删除后一定余的是主元素。这里给的ArrayList类型数组，好像在提醒用这个方法。
ArrayList不熟悉，多少尝试都失败，在网上看到，通过记录一个元素出现的次数，是这个元素时候计数器+1，不是的时候-1，当时0的时候重新计数，这是01的原则，也实现了同时删除两个数，最后的计数器对于的元素就是答案。
Java程序：
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
int numsLen = nums.size();
if(numsLen==1)
return nums.get(0);
int times=0;
int maj = 0;
for(int i=0;i<numsLen;i++){
if(times==0){
maj = nums.get(i);
times= 1;
}else{
if(maj==nums.get(i))
times++;
else
times--;
}
}
return maj;
}
}
总耗时: 2373 ms
这里也要求这个元素出现次数大于len/2,否则，可在在刚开始就剔除了这个元素，如[1,1,1,2,2,3,3,4,4,5],这个结果就是4了。
Python程序：
class Solution:
"""
@param nums: A list of integers
@return: The majority number
"""
def majorityNumber(self, nums):
# write your code here
numsLen = len(nums)
if numsLen == 1 :
return nums[0]
times = 0
maj = 0
for num in nums:
if times==0:
times=1
maj = num
elif maj==num:
times +=1
else:
times -=1
return maj
总耗时: 350 ms
在这里看到，可以求第二多的元素
Java程序：
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
int first = Integer.MIN_VALUE; // the number with the top votes
int firstVote = 0; // the top votes
int second = Integer.MIN_VALUE; // the number with the second top votes
int secondVote = 0; // the second top votes
int numsLen = nums.size();
if(numsLen==1)
return nums.get(0);
for(int i=0;i<numsLen;i++){
if(firstVote > 0 && nums.get(i) == first) {
firstVote++;
} else if(secondVote > 0 && nums.get(i) == second) {
secondVote++;
if(secondVote > firstVote) {
int t = first;
first = second;
second = t;
t = firstVote;
firstVote = secondVote;
secondVote = t;
}
} else if(firstVote == 0) {
first = nums.get(i);
firstVote++;
} else if(secondVote == 0) {
second = nums.get(i);
secondVote++;
} else {
firstVote--;
secondVote--;
}
}
// confirm if the number with top 2 votes occurs more than 3/n times
// int firstCount = 0;
// int secondCount = 0;
// for(int i=0;i<numsLen;i++) {
// if(firstVote > 0 && nums.get(i) == first) firstCount++;
// if(secondVote > 0 && nums.get(i) == second) secondCount++;
// }
// if(firstCount > numsLen / 3) return first;
// else if(secondCount > numsLen / 3) return second;
// else return 0;
return first;
}
}
总耗时: 1864 ms
寻找缺失的数
题目：
给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。
样例
N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。
注意
可以改变序列中数的位置。
挑战
在数组上原地完成，使用O(1)的额外空间和O(N)的时间。
Java程序：
官方给的C++,改写成java运行超时
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int findMissing(int[] nums) {
// write your code here
nums = bucket_sort(nums);
int n = nums.length;
for(int i=0;i<n;++i){
if(nums[i] != (i+1))
return i+1;
}
return n+1;
}
public int[] bucket_sort(int [] nums){
int n = nums.length;
for(int i=0;i<n;++i){
while(nums[i] !=i+1){
if(nums[i]<=0 ||nums[i]>n || nums[i] ==nums[nums[i]-1])
break;
int tmp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[nums[i] - 1] =tmp;
}
}
return nums;
}
}
异或更简单，因为 i^i = 0
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int findMissing(int[] nums) {
// write your code here
if(nums == null || nums.length == 0)
return 0;
int result = 0;
for(int i = 0;i<nums.length;i++){
result^=i;
result^=nums[i];
}
result^=nums.length;
return result;
}
}