수조 기초 문제

1.Sum of the array numbers

int sum(int[] nums) {
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        result += nums[i];
    }
    return result;
}

2.Minimum element of the array

int minimum(int a , int b) {
    if (a < b) {
        return a;
    }
    return b;
}

int minimum(int[] nums) {
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;
}

3.Second minimum element of the array

int secondMinimum(int[] nums) {
    int min = Math.min(nums[0],nums[1]);
    int secondMin = Math.max(nums[0],nums[1]);
    for (int i = 2; i < nums.length; i++) {
        if (nums[i] < min) {
            secondMin = min;
            min = nums[i];
        } else if (nums[i] == min) {
            secondMin = min;
        } else if (nums[i] > min && nums[i] < secondMin) {
            secondMin = nums[i];
        } else if (nums[i] == secondMin) {
            continue;
        } else {
            continue;
        }
    }
    return secondMin;
}

4.Reverse Array

// ， 
public void reverseArray(int[] nums) {
    int first = 0, end = nums.length - 1;
    while (first < end) {
        swap(nums,first++,end--);
    }
}
private void swap(int[] nums, int first, int second) {
    // first second ， 
    int temp = nums[first];
    nums[first] = nums[second];
    nums[second] = temp;
}

5.Odd Even Sort 홀수는 앞에 있고 짝수는 뒤에 있습니다.

public void oddEvenSort(int[] nums) {
    int first = 0, second = nums.length-1;
    while (first < second) {
        while (first < second && nums[fisrt] % 2 == 1) {
            first++;// & first < second 
        }
        while (first < second && nums[second] % 2 == 0) {
            second--;
        }
        if (first < second) {
            swap(nums,first++,second--);
        }
    }
}

6. Pivot Sort는 한 개의 수를 찾아낸다. 왼쪽의 수는 모두 그보다 작고, 오른쪽의 수는 모두 그보다 크다.

public void pivotSort(int[] nums, int pivot) {
    int first = 0, second = nums.length - 1;
    while (first < second && nums[first] <= pivot) {
        first++;
    }
    while (first < second && nums[second] > pivot) {
        second--;
    }
    if (first < second) {
        swap(nums,first++,second--);
    }
}
public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

7. Element 앞뒤 포인터를 제거하고 삭제할 요소를 마지막에 놓습니다.first 바늘은 왼쪽부터 세고, 같지 않으면 건너뛰고, 같지 않으면 오른쪽과 목표 값과 같지 않은 원소를 교환합니다.

public int removeElement(int[] nums, int val) {
    if (nums.length == 0) {
        return 0;
    }
    int first = 0, second = nums.length - 1;
    while (first < second) {
        while (first < second && nums[first] != val) {
            first++;
        }
        while (first < second && nums[second] == val) {
            // 
            second--;
        }
        if (first < second) {
            swap(nums,first++,second--);
        }
    }
    return return nums[first] != val ? first+1 : first;// [3,2,2,3] 3， first second
}
//Solution2 for remvoe element
public int removeElement(int[] nums, int val) {
    int index = 0, len = nums.length;
    //len is the valid length of remaining array
    while (index < len) {
        if (nums[index] == val) {
            len--;//remove one element
            //Keep the possible valid element
            nums[index] = nums[len];
        } else {
            index++;
        }
    }
    return len;
}

8.Merge Two Sorted Array

// ， ， ， ， result nums1 。 。 nums2 nums1， 
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] result = new int[m + n];
        int i = 0, j = 0, index = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                result[index++] = nums1[i++];
            } else {
                result[index++] = nums2[j++];
            }
        }
        while (i < m) {
            result[index++] = nums1[i++];
        }
        while (j < n) {
            result[index++] = nums2[j++];   
        }
        for (i = 0; i < m + n; i++) {
            nums1[i] = result[i];
        }
        
    }
}

solution: 병합 정렬, 나누어 다스리다

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        result = []
        left, right = 0, 0
        while left < m and right < n:
            if nums1[left] < nums2[right]:
                result.append(nums1[left])
                left += 1
            else:
                result.append(nums2[right])
                right += 1
         #        
        while left < m:
            result.append(nums1[left])
            left += 1
        
        while right < n:
            result.append(nums2[right])
            right += 1
            
        for i in range(m + n):
            nums1[i] = result[i]
            

설명: [Sort Integer II]http://www lintcode.com/en/problem/sort-integers-ii/
solution: 병합 정렬, 여기는 원래 수조를 바탕으로 버퍼가 생성된 것이지 새로운 수조를 생성하는 것이 아닙니다. 차이점에 주의하십시오.

class Solution:
    """
    @param A: an integer array
    @return: nothing
    """
    def sortIntegers2(self, A):
        # write your code here
         m = len(A)
         temp = [0 for _ in range(m)]
         self.mergeSort(A, 0, m - 1, temp)
         
    def mergeSort(self, A, start, end, temp):
        if start >= end:
            return 
        
        mid = (start + end) / 2
        # ， 
        self.mergeSort(A, start, mid, temp)
        self.mergeSort(A, mid + 1, end, temp)
        # " "， 
        self.merge(A, start, end, temp)
        
    def merge(self, A, start, end, temp):
        mid = (start + end) / 2
        
        left, right = start, mid + 1
        # temp buffer ， append， （ ）
        index = start
        while left <= mid and right <= end:
            
            if A[left] < A[right]:
                temp[index] = A[left]
                left += 1
                index += 1
            else:
                temp[index] = A[right]
                right += 1
                index += 1
        
        while left <= mid:
            temp[index] = A[left]
            left += 1
            index += 1
            
        while right <= end:
            temp[index] = A[right]
            right += 1
            index += 1
            
        for index in range(start, end + 1):
            A[index] = temp[index]

solution2: 빠른 배열, 병합 정렬 공간보다 복잡도가 낮습니다. 추가 수조는 필요 없습니다. pivot 선택에 주의하십시오.

class Solution:
    # @param {int[]} A an integer array
    # @return nothing
    def sortIntegers2(self, A):
        # Write your code here
        self.quickSort(A, 0, len(A) - 1)
    
    def quickSort(self, A, start, end):
        if start >= end:
            return
        
        left, right = start, end
        # key point 1: pivot is the value, not the index
        pivot = A[(start + end) / 2]

        # key point 2: every time you compare left & right, it should be 
        # left <= right not left < right
        while left <= right:
            while left <= right and A[left] < pivot:
                left += 1
            
            while left <= right and A[right] > pivot:
                right -= 1
            
            if left <= right:
                A[left], A[right] = A[right], A[left]
                
                left += 1
                right -= 1
        
        self.quickSort(A, start, right)
        self.quickSort(A, left, end)